10
$\begingroup$

The title is somewhat "arrogant": say, most of us treat $P\neq NP$ as an "obvious" fact, albeit no proof is in sight. But my question is at a much, much lower level, is about a fact which "should be" indeed obvious.

A circuit over a semiring $R$ is a conventional circuit which uses the two semiring operations as gates. I am mostly interested in circuits over the tropical $(\min,+)$ and $(\max,+)$ semirings with $R={\mathbb R}_+$, just because they can simulate most of the fundamental dynamic programming (DP) algorithms.

A majority vote function is a partially defined function $\mathrm{Maj}(x_1,\ldots,x_m)$ which outputs that element $x_i$ (if there is one) which appears more than $m/2$ times in the input string.

Question : Can one additional majority vote gate to output the result substantially reduce the size of tropical circuits?
Under "substantially" I mean something really big, say, by some super-polynomial (in the number $n$ of variables of circuits) factor.

Over semirings, where $\mathrm{Maj}$ is easily computable (like over the boolean semiring), the answer is clear NO. Sometimes, even when $\mathrm{Maj}$ itself is not computable - like in arithmetic circuits - the answer is NO: one of the gates entering the output $\mathrm{Maj}$ gate must compute the target polynomial correctly on a large fraction of inputs. And Zarankiewicz-type arguments imply that if the values of two polynomials coincide on a "large" number of inputs, then they must coincide on all inputs: if a polynomial $f$ vanishes on a rectangle $S_1\times\cdots\times S_n$ with all $|S_i|$ larger than the degree, then $f$ is a zero polynomial. Zarankiewicz-type arguments ensure the presence of such large rectangles.

But what about tropical circuits? Zarankiewicz-type arguments do not work here: unlike in the case of arithmetic circuits, here the distribution (larger/smaller) of values $x_i$ in inputs $x\in {\mathbb R}^n$ is critical. The answer to my question "should" be still NO also in the case of tropical circuits, just because the YES answer would be a real breakthrough in dynamic programming: we could substantially speed-up DP algorithms by just running several of them in parallel, and by taking a majority vote. But how to show this NO?

N.B. We can easily compute $\mathrm{Maj}(x_1,\ldots,x_m)$, if we allow additional boolean valued gates $[\rho]:{\mathbb R}^2\to\{0,1\}$ for binary relations, where $[\rho](x,y)=1$ iff $x\rho y$. Namely, we can first compute the numbers $z_i:= \sum_{j=1}^m [x_j=x_i]$, and then output the maximum or the minimum of $x_i\cdot [z_i>m/2]$ over all $i=1,\ldots,m$ (the most popular value, if there is one, is unique). So, my question seems like a "purely technical" one: the problem is that neither predicates $[\rho]$ nor multiplication by their outputs is allowed in tropical circuits. But then the question is even more "disturbing": how can we hope to solve "big" problems without being able to solve "merely technical" ones? I therefore hope that someone knows at least some "high level" argument(s) towards the NO answer.

P.S. [added] Majority vote output gates $\mathrm{Maj}$ come naturally in play when derandomizing probabilistic circuits: take many copies, apply Chernoff, and take a majority vote.

P.P.S. [added 27.05] I would like to slightly "focus" my question. If $T_m(f)$ and $T(f)$ denote, respectively, the tropical circuit complexity of a polynomial $f$ with and without $\mathrm{Maj}$ output gate, then my question turns into "can the gap $T(f)/T_m(f)$ be superpolynomial?". A partial answer is NO if the gap $T(f)/B(f)$ is small, where $B(f)$ denotes the monotone boolean circuit complexity of the boolean version of the polynomial $f$.

If $T(f)\leq g(n)\cdot B(f)$, then $T(f)\leq cn\cdot g(n)\cdot T_m(f)$ for a constant $c$.

Proof: The boolean version of $f$ can be computed by a monotone boolean circuit with $t:=T_m(f)$ gates with a majority output gate of $\leq t$ inputs (just take a boolean version of a tropical circuit). In the boolean case, majority is easy: $B(\mathrm{Maj}_t)$ is at most about $t\log t$. So, $B(f)$ is also at most about $t\log t\leq tn$. Q.E.D.

So, the only "dangerous" in my question are polynomials $f$ with very large gaps $T(f)/B(f)$, like the spanning tree polynomial (where this gap is exponential): for this polynomial $f$, we have $T(f)=2^{\Omega(n)}$ [Jerrum and Snir], but $B(f)=O(n^3)$ [Floyd-Warshall DP algorithm for graph connectivity].

|cite|improve this question
$\endgroup$
  • $\begingroup$ Obviously you want a function that can be computed over the tropical semi-ring without Maj gates (otherwise Maj itself would be an example). My gut is that the output of a nontrivial Maj gate is never a tropical polynomial (trivial = Maj w/ all inputs identical), because it will not admit a partition of $\mathbb{R}^n$ into full-dimensional convex sets on which it is linear, but every tropical polynomial has this property. If this is right, then Maj can never give a speed-up in the tropical setting. Have I done something silly here? $\endgroup$ – Joshua Grochow Apr 25 '17 at 23:51
  • $\begingroup$ Are there other semirings in the same class? This kind of tropical semiring seems to obey the multiplicative semi-idempotence identity $x\otimes y \le x\otimes x\otimes y$ (where $\otimes$ is the multiplication operation) but not multiplicative idempotence $x\otimes x = x$. Assuming $\mathbb{R}_{+}$ means the non-negative reals, these semirings also satisfy $1\oplus x = 1$ (where $\oplus$ is addition and $1$ is the multiplicative identity). $\endgroup$ – András Salamon Apr 26 '17 at 7:34
  • $\begingroup$ @Joshua: Yes, Maj is neither convex nor concave, so it is not a tropical polynomial, and therefore cannot be computed by a tropical circuit at all. But I cannot see how this (impossibility to simulate Maj) should exclude a potential speed-up when allowing Maj? $\endgroup$ – Stasys Apr 26 '17 at 9:14
  • $\begingroup$ @Andras: "cousins" of tropical semirings are bottleneck max-min and min-max semirings over, say, natural numbers. So, my question applies also to these semirings. Unlike tropical circuits, bottleneck circuits can sort numbers, but they still cannot detect most popular ones. $\endgroup$ – Stasys Apr 26 '17 at 9:34
  • 2
    $\begingroup$ @Stasys: On a little further thought, my gut was wrong. For example, take $p = \max(x+4,2x+4,4x), q = \max(x+4,3x+2), r = \max(4,2x+4,3x+2)$, then $Maj(p,q,r) = \max(x+4,2x+4,3x+2)$ which is not equal to any of $p,q,r$ (indeed, $p=q \neq r$ on $[-\infty,0]$, $p=r \neq q$ on $[0,2]$, and $p \neq q=r$ on $[2,\infty]$). $\endgroup$ – Joshua Grochow Apr 26 '17 at 19:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.