15
$\begingroup$

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.

Improve this question
$\endgroup$
15
  • 2
    $\begingroup$ As for Question 1, what about adding 1 to a polynomial which is hard to count? $\endgroup$
    – Tsuyoshi Ito
    Oct 25, 2014 at 1:25
  • 2
    $\begingroup$ Your three questions seem distinct enough that they should be three separate questions. $\endgroup$
    – David Richerby
    Oct 25, 2014 at 9:07
  • $\begingroup$ 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.) $\endgroup$
    – Tsuyoshi Ito
    Oct 25, 2014 at 11:54
  • $\begingroup$ ‘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) $\endgroup$
    – Tsuyoshi Ito
    Oct 25, 2014 at 12:20
  • 1
    $\begingroup$ @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? $\endgroup$
    – Stasys
    Oct 25, 2014 at 13:07

1 Answer 1

Reset to default
7
$\begingroup$

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

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ A nice answer, thanks! $\endgroup$
    – Stasys
    Feb 9, 2020 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.