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].