Let $\vec{S}$ be a state vector given as $\vec{S} = \{S_1…S_i…S_m\}$, where $S_i$ is some state and can take $k_i$ distinct values. Hence we have $\prod_{i}k_i$ possible states for $\vec{S}$. Now, I have summation of the following form :
$$\sum_{\vec{S}} \prod_{i\le j}F(S_i,S_j)$$
Is there any hope of doing this sum in polynomial steps w.r.t $m$ ?
For a similar case please check this question. But there the function $F$ is unary and hence the case becomes easy.
Example: Let $\vec{S}=\{S_1,S_2,S_3\}$ be the state vector and let $S_i$ take $k_i$ values. Then our summation is the following:
$$\sum_{S_1}\sum_{S_2}\sum_{S_3}F(S_1,S_2)F(S_2,S_3)F(S_1,S_3)$$
In case m-step solution is not possible. Then can I get an upper and lower bound ?
Best Answer
Here is a partial negative answer. Take the special case where the $S_i$s are all equal to $\{1,\ldots,k\}$, and $F(i,j)$ takes only values $0$ or $1$ with $F(i,i)=0$ and $F(i,j) = F(j,i)$.
Then each choice of $F$ corresponds to a different undirected graph on $k$ vertices, and the formula counts the number of $m$-cliques in the graph. This is considered to be a hard problem for even modestly large $m$. This recent paper looks like it should have good references.
In particular the NP-completeness of the clique problem dashes any hopes for a strongly polynomial algorithm. However it doesn’t quite rule out the possibility that for a given fixed $k$ and a fixed $F$ there could be some way to compute that scales well with $m$. For this graph example the sum is identically $0$ for all $m>k$.