9
$\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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.