<p>(I am posting my comments as an answer in response to the OP’s request.)</p>

<p>As for Question 1, let <i>f</i><sub><i>n</i></sub>: {0,1}<sup><i>n</i></sup>→ℕ be a family of functions whose arithmetic circuit requires exponential size.  Then so does <i>f</i><sub><i>n</i></sub>+1, but <i>f</i><sub><i>n</i></sub>+1 is easy to decide by a trivial monotone arithmetic circuit.  If you prefer to avoid constants in monotone arithmetic circuits, then let <i>f</i><sub><i>n</i></sub>: {0,1}<sup><i>n</i></sup>→ℕ be a family of functions such that the arithmetic circuit for <i>f</i><sub><i>n</i></sub> requires exponential size and <i>f</i><sub><i>n</i></sub>(0, …, 0)=0, and consider <i>f</i><sub><i>n</i></sub>+<i>x</i><sub>1</sub>+…+<i>x</i><sub><i>n</i></sub>.</p>

CC BY-SA 4.0
2020-02-09T19:51:42.433Z
A nice answer, thanks!
Stasys
CC BY-SA 3.0
2014-10-25T22:30:23.903Z
2014-10-25T22:30:23.903Z
Tsuyoshi Ito
<p>Every monotone <a href="http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity" rel="nofollow">arithmetic circuit</a>, 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</p>

<ul>
<li> <b>computes</b> $f$ if $F(a)=f(a)$ holds for all $a\in \mathbb{N}^n$;
<li> <b>counts</b> $f$ if $F(a)=f(a)$ holds for all $a\in\{0,1\}^n$;
<li> <b>decides</b> $f$ if $F(a)&gt;0$ exactly when $f(a)&gt;0$ holds for all  $a\in\{0,1\}^n$.
</ul> 

<p>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".</p>

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

<p>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 <i>decided</i> 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 <i>computing</i> PATH must have size $2^{\Omega(n)}$.
 <p>
 On the other hand, every circuit <i>counting</i>
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 <a href="http://de.wikipedia.org/wiki/Sharp-P" rel="nofollow">$\#$<b>P</b>-complete problem</a>. So, we all "believe" that PATH cannot have any counting $\{+,\times\}$-circuits of polynomial size. The "only" problem is to <i>prove</i> this ...
<p>
I can show that every $\{+,\times\}$-circuit counting a related <i> Hamiltonian path</i> polynomial HP requires exponential size. Monomials of this polynomial correspond to $1$-to-$n$ paths in $K_n$ containing
all nodes. 
Unfortunately, the <a href="http://epubs.siam.org/doi/abs/10.1137/0208032" rel="nofollow">reduction</a> of $\#$HP to $\#$PATH by Valiant requires to compute the inverse of the Vandermonde matrix, and hence cannot be implemented by a $\{+,\times\}$-circuit.</p>

<blockquote>
<b>Question 2:</b> Has anybody seen a <b>monotone</b> reduction of $\#$HP to $\#$PATH?
</blockquote>

<p>And finally: </p>

<blockquote>
<b>Question 3:</b> Was a "monotone version" of the class $\#$<b>P</b> considered at all? 
</blockquote>

<p><b>N.B.</b> Note that I am talking about a very restricted class of circuits: <i>monotone</i> 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 $\#$<b>P</b>-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)}$. 
<p>
<b>ADDED:</b>  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. </p>

CC BY-SA 3.0
2014-10-25T01:25:06.627Z
As for Question 1, what about adding 1 to a polynomial which is hard to count?
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-25T09:07:32.110Z
Your three questions seem distinct enough that they should be three separate questions.
David Richerby
CC BY-SA 3.0
2014-10-25T11:54:55.343Z
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.)
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-25T12:20:39.867Z
‘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)
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-25T12:25:41.423Z
In other words, #P-completeness of #Matching is interesting not because it shows existence of a counting problem whose decision version is easy.  In grad school, I once discussed with colleagues if there is any formal reason why #P-completeness of #Matching is more interesting than #P-completeness of #SAT+1, and we could not come up with any.  So I am very curious to know if there is one.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-25T13:07:03.263Z
@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?
Stasys
CC BY-SA 3.0
2014-10-25T13:08:04.837Z
My motivation for all 3 questions was actually the PATH polynomial. I.e. to prove an exponential bound for {+,x}-circuits counting this polynomial. Say, via monotone reduction to HP or via a direct proof. This shouldn't be too hard. Much harder seems to come up with an $\Omega(n^3)$ lower bound for circuits deciding this polynomial. This would show that Bellman-Ford and Floyd-Warshal DP shortest path algorithms are optimal if only Min and Plus operations are used. P.S. I also do not see why Matching should be more interesting than 3SAT+1 in this respect (mere separation of concepts).
Stasys
CC BY-SA 3.0
2014-10-25T16:03:25.450Z
@TsuyoshiIto: Here is a formal reason the #P-completeness of #Matching is more interesting than that of #3SAT+1. (An informal reason is that #Matching is a natural problem, whereas #3SAT+1 clearly was unnaturally modified...) The language corresponding to #3SAT+1 is all strings, whereas the language corresponding to #Matching is nontrivial. More than that, the MATCHING language isn't sparse, and I believe it isn't co-sparse either. (But my guess is: the real historical interest in the #P-completeness of #Matching was because it was a natural problem.)
Joshua Grochow
CC BY-SA 3.0
2014-10-25T16:18:57.303Z
@David Richerby: I agree. Say, Tsuyoshi has essentially answered Q1, but the bunch Q2+Q3 might be interesting in itself.
Stasys
CC BY-SA 3.0
2014-10-25T16:19:40.127Z
@Joshua Grochow: by exactly this reason (being "natural") the decision complexity of PATH is more interesting than that of, say, HP+the sum of all variables. But as long as we are only interested in "separating concepts", not in "understanding *reasons* of complexity of specific problems" - any artificial creature seems to be ok.
Stasys
CC BY-SA 3.0
2014-10-25T17:09:11.697Z
think these are deep/ barely answerable questions as usual from SJ but also that they are written in too much abbreviated "insider" shorthand & crosscutting multiple separately studied fields & are hard to parse because of that. eg in particular section starting "as a possible candidate..." needs to be fleshed out more formally/ detailed; cant quite follow. also it would help to point to analogous proofs in the literature. suggest further [chat]
vzn
CC BY-SA 3.0
2014-10-25T17:34:39.663Z
@Stasys: I didn't mean to say that this question or that an artificial answer to this question wasn't a good one (in fact, I think this is a *great* question and am happy with Tsuyoshi's example). I was just answering Tsuyoshi Ito's question about why the #P-completeness of #Matching is more interesting than that of #3SAT+1.
Joshua Grochow
CC BY-SA 3.0
2014-10-25T18:00:44.760Z
@Joshua Grochow: to not being misunderstood. In your comment, you just said what I also wanted to answer: one deal is to separate two classes by an "artificial" example, the other is doing this by a "natural" one. The first tells only about classes, the second about the *reasons of complexity*. Separating classes and proving lower bounds are still very different things. The latter helps the former, but not otherwise. B.t.w. (to add yet another argument to your comment) Matching is also interesting because it separates monotone "decision" world from non-monotone (as shown by Razborov).
Stasys
CC BY-SA 3.0
2014-10-25T18:28:15.243Z
@vzn: I think there is no need in a chat. Q1 is already answered (by Tsuyoshi). Q2+Q3 are only about references (if somebody knows them).
Stasys
CC BY-SA 3.0
2014-10-26T03:16:26.067Z
@Joshua Grochow: Thanks, that is definitely one formal difference.  Unfortunately, it does not answer the original motivation of our conversation at that time (which I did not write here), but because I already wrote too much in comments here, I will shut up.
Tsuyoshi Ito
<circuit-complexity><lower-bounds><arithmetic-circuits><cc-complexity-theory>
Any polynomial which is hard to count but easy to decide?
Stasys
# Any polynomial which is hard to count but easy to decide?

(Asked by: username_0 on 2014-10-24)

Every monotone [arithmetic circuit](http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity), 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](http://de.wikipedia.org/wiki/Sharp-P). 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](http://epubs.siam.org/doi/abs/10.1137/0208032) 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:** username_1 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.

**Tags:** circuit-complexity, lower-bounds, arithmetic-circuits, cc-complexity-theory

> **Comments:**
> **username_1**: As for Question 1, what about adding 1 to a polynomial which is hard to count?  
> **username_2**: Your three questions seem distinct enough that they should be three separate questions.  
> **username_1**: 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.)  
> **username_1**: ‘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)  
> **username_1**: In other words, #P-completeness of #Matching is interesting not because it shows existence of a counting problem whose decision version is easy.  In grad school, I once discussed with colleagues if there is any formal reason why #P-completeness of #Matching is more interesting than #P-completeness of #SAT+1, and we could not come up with any.  So I am very curious to know if there is one.  
> **username_0**: @username_1: 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?  
> **username_0**: My motivation for all 3 questions was actually the PATH polynomial. I.e. to prove an exponential bound for {+,x}-circuits counting this polynomial. Say, via monotone reduction to HP or via a direct proof. This shouldn't be too hard. Much harder seems to come up with an $\Omega(n^3)$ lower bound for circuits deciding this polynomial. This would show that Bellman-Ford and Floyd-Warshal DP shortest path algorithms are optimal if only Min and Plus operations are used. P.S. I also do not see why Matching should be more interesting than 3SAT+1 in this respect (mere separation of concepts).  
> **username_3**: @TsuyoshiIto: Here is a formal reason the #P-completeness of #Matching is more interesting than that of #3SAT+1. (An informal reason is that #Matching is a natural problem, whereas #3SAT+1 clearly was unnaturally modified...) The language corresponding to #3SAT+1 is all strings, whereas the language corresponding to #Matching is nontrivial. More than that, the MATCHING language isn't sparse, and I believe it isn't co-sparse either. (But my guess is: the real historical interest in the #P-completeness of #Matching was because it was a natural problem.)  
> **username_0**: @username_2: I agree. Say, Tsuyoshi has essentially answered Q1, but the bunch Q2+Q3 might be interesting in itself.  
> **username_0**: @username_3: by exactly this reason (being "natural") the decision complexity of PATH is more interesting than that of, say, HP+the sum of all variables. But as long as we are only interested in "separating concepts", not in "understanding *reasons* of complexity of specific problems" - any artificial creature seems to be ok.  
> **username_4**: think these are deep/ barely answerable questions as usual from SJ but also that they are written in too much abbreviated "insider" shorthand & crosscutting multiple separately studied fields & are hard to parse because of that. eg in particular section starting "as a possible candidate..." needs to be fleshed out more formally/ detailed; cant quite follow. also it would help to point to analogous proofs in the literature. suggest further [chat]  
> **username_3**: @username_0: I didn't mean to say that this question or that an artificial answer to this question wasn't a good one (in fact, I think this is a *great* question and am happy with Tsuyoshi's example). I was just answering username_1's question about why the #P-completeness of #Matching is more interesting than that of #3SAT+1.  
> **username_0**: @username_3: to not being misunderstood. In your comment, you just said what I also wanted to answer: one deal is to separate two classes by an "artificial" example, the other is doing this by a "natural" one. The first tells only about classes, the second about the *reasons of complexity*. Separating classes and proving lower bounds are still very different things. The latter helps the former, but not otherwise. B.t.w. (to add yet another argument to your comment) Matching is also interesting because it separates monotone "decision" world from non-monotone (as shown by Razborov).  
> **username_0**: @username_4: I think there is no need in a chat. Q1 is already answered (by Tsuyoshi). Q2+Q3 are only about references (if somebody knows them).  
> **username_1**: @username_3: Thanks, that is definitely one formal difference.  Unfortunately, it does not answer the original motivation of our conversation at that time (which I did not write here), but because I already wrote too much in comments here, I will shut up.  

---

## 1 answers

### Answer by username_1 on 2014-10-25. Score: 7 | Accepted answer

(I am posting my comments as an answer in response to the OP’s request.)

As for Question 1, let *f**n*: {0,1}*n*→ℕ be a family of functions whose arithmetic circuit requires exponential size. Then so does *f**n*+1, but *f**n*+1 is easy to decide by a trivial monotone arithmetic circuit. If you prefer to avoid constants in monotone arithmetic circuits, then let *f**n*: {0,1}*n*→ℕ be a family of functions such that the arithmetic circuit for *f**n* requires exponential size and *f**n*(0, …, 0)=0, and consider *f**n*+*x*1+…+*x**n*.

> **Comments:**
> **username_0**: A nice answer, thanks!  

---

