<p>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 <i>lower</i> level, is about a fact which "should be" indeed obvious.
<p> 
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.
<p>
A <i>majority vote function</i> 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.</p>

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

<p>Over semirings, where $\mathrm{Maj}$ is easily computable (like over the <i>boolean</i> semiring), the answer is clear NO. Sometimes,
even when $\mathrm{Maj}$ itself is not computable - like in <i>arithmetic</i> 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.
<p>
But what about <i>tropical</i> circuits? Zarankiewicz-type arguments do not work here: unlike in the case of arithmetic circuits, here the <i>distribution</i> (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 <b>how</b> to show this NO?
<p>
<b>N.B.</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&gt;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>
<b>P.S.</b> [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>
<b>P.P.S.</b> [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 <i>partial</i> 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$. </p>

<blockquote>
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$.
</blockquote>

<p><b>Proof:</b> 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.
<p>
So, the only "dangerous" in my question are polynomials $f$ with very <i>large</i> 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)}$ [<a href="http://dx.doi.org/10.1145/322326.322341" rel="noreferrer">Jerrum and Snir</a>], but $B(f)=O(n^3)$ [Floyd-Warshall DP algorithm for graph connectivity].</p>

CC BY-SA 3.0
2017-04-25T23:51:04.620Z
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?
Joshua Grochow
CC BY-SA 3.0
2017-04-26T07:34:33.260Z
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).
András Salamon
CC BY-SA 3.0
2017-04-26T09:14:01.140Z
@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?
Stasys
CC BY-SA 3.0
2017-04-26T09:34:10.257Z
@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.
Stasys
CC BY-SA 3.0
2017-04-26T13:29:20.350Z
My point was not just that Maj itself isn't a tropical polynomial, but that Maj applied to any non-trivial set of tropical polynomials isn't a tropical polynomial. This implies no speedup because given a tropical poly f, there is no tropical circuit with Maj as output gate that computes f.
Joshua Grochow
CC BY-SA 3.0
2017-04-26T19:47:01.053Z
@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]$).
Joshua Grochow
CC BY-SA 3.0
2017-04-27T15:06:13.983Z
@Joshua: a nice example! Thanks also for further private elaboration of the idea which led to this (interesting albeit "killed" by your example) claim.
Stasys
CC BY-SA 3.0
2017-04-28T11:52:22.473Z
@Andras: I just realized that max-min circuits *can* compute the majority vote of 2m inputs: sort these inputs, and output the m-th element. So, for bottleneck circuits, the answer to my question is "no big speedup" (I was wrong in my comment).
Stasys
<cc.complexity-theory><co.combinatorics><circuit-complexity><lower-bounds><dynamic-programming>
How to prove "obvious" facts?
Stasys
# How to prove "obvious" facts?

(Asked by: username_0 on 2017-04-25)

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](http://dx.doi.org/10.1145/322326.322341)], but $B(f)=O(n^3)$ [Floyd-Warshall DP algorithm for graph connectivity].

**Tags:** cc.complexity-theory, co.combinatorics, circuit-complexity, lower-bounds, dynamic-programming

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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).  
> **username_0**: @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?  
> **username_0**: @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.  
> **username_1**: My point was not just that Maj itself isn't a tropical polynomial, but that Maj applied to any non-trivial set of tropical polynomials isn't a tropical polynomial. This implies no speedup because given a tropical poly f, there is no tropical circuit with Maj as output gate that computes f.  
> **username_1**: @username_0: 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]$).  
> **username_0**: @Joshua: a nice example! Thanks also for further private elaboration of the idea which led to this (interesting albeit "killed" by your example) claim.  
> **username_0**: @Andras: I just realized that max-min circuits *can* compute the majority vote of 2m inputs: sort these inputs, and output the m-th element. So, for bottleneck circuits, the answer to my question is "no big speedup" (I was wrong in my comment).  

---

## 0 answers

