# Any polynomial which is hard to count but easy to decide?

Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial $f(x_1,\ldots,x_n)$, the circuit

• computes $f$ if $F(a)=f(a)$ holds for all $a\in \mathbb{N}^n$;
• counts $f$ if $F(a)=f(a)$ holds for all $a\in\{0,1\}^n$;
• decides $f$ if $F(a)>0$ exactly when $f(a)>0$ holds for all $a\in\{0,1\}^n$.

I know explicit polynomials $f$ (even multilinear) showing that the circuit-size gap "computes/counts" can be exponential. My question concerns the gap "counts/decides".

Question 1: Does anybody know of any polynomial $f$ which is exponentially harder to count than to decide by $\{+,\times\}$-circuits?

As a possible candidate, one could take the PATH polynomial whose variables correspond to edges of the complete graph $K_n$ on $\{1,\ldots,n\}$, and each monomial corresponds to a simple path from node $1$ to node $n$ in $K_n$. This polynomial can be decided by a circuit of size $O(n^3)$ implementing, say, the Bellman-Ford dynamic programming algorithm, and it is relatively easy to show that every $\{+,\times\}$-circuit computing PATH must have size $2^{\Omega(n)}$.

On the other hand, every circuit counting PATH solves the $\#$PATH problem, i.e. counts the number of $1$-to-$n$ paths in the specified by the corresponding $0$-$1$ input subgraph of $K_n$. This is a so-called $\#$P-complete problem. So, we all "believe" that PATH cannot have any counting $\{+,\times\}$-circuits of polynomial size. The "only" problem is to prove this ...

I can show that every $\{+,\times\}$-circuit counting a related Hamiltonian path polynomial HP requires exponential size. Monomials of this polynomial correspond to $1$-to-$n$ paths in $K_n$ containing all nodes. Unfortunately, the reduction of $\#$HP to $\#$PATH by Valiant requires to compute the inverse of the Vandermonde matrix, and hence cannot be implemented by a $\{+,\times\}$-circuit.

Question 2: Has anybody seen a monotone reduction of $\#$HP to $\#$PATH?

And finally:

Question 3: Was a "monotone version" of the class $\#$P considered at all?

N.B. Note that I am talking about a very restricted class of circuits: monotone arithmetic circuits! In the class of $\{+,-,\times\}$-circuits, Question 1 would be just unfair to ask at all: no lower bounds larger than $\Omega(n\log n)$ for such circuits, even when required to compute a given polynomial on all inputs in $\mathbb{R}^n$, are known. Also, in the class of such circuits, a "structural analogue" of Question 1 -- are there $\#$P-complete polynomials which can be decided by poly-size $\{+,-,\times\}$-circuits? -- has an affirmative answer. Such is, for example, the permanent polynomial PER$=\sum_{h\in S_n}\prod_{i=1}^n x_{i,h(i)}$.

ADDED: Tsuyoshi Ito answered Question 1 with a very simple trick. Still, Questions 2 and 3 remain open. The counting status of PATH is interesting in its own both because it is a standard DP problem and because it is #P-complete.

• As for Question 1, what about adding 1 to a polynomial which is hard to count? Oct 25, 2014 at 1:25
• Your three questions seem distinct enough that they should be three separate questions. Oct 25, 2014 at 9:07
• I am afraid that you cannot avoid trivial examples by merely forbidding constants in arithmetic circuits. How about adding x_1+…+x_n to a hard-to-count polynomial which takes 0 at the origin? (Moreover, if you forbid constants, you cannot represent a polynomial which takes a nonzero value at the origin.) Oct 25, 2014 at 11:54
• ‘As in the "#P theory", under "decision" we mean "is there at least one solution". And constants are not solutions (usually).’ You know, you are on a slippery slope here. Consider a #P counterpart of Question 1: give an example of relations R∈FNP such that #R is #P-complete but it is easy to decide whether #R(x)>0 or not. We may be tempted to say Matching, but this is an overkill. Adding a trivial solution to 3SAT works just fine, and my previous comment is analogous to this. (more) Oct 25, 2014 at 12:20
• @Tsuyoshi Ito: Well, your simple trick (add the sum of all variables to a hard to count polynomial) actually answers Question 1 (in the form it was stated). Could you put it as an answer? Oct 25, 2014 at 13:07