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].
How to prove obvious facts?
cc.complexity theory;co.combinatorics;circuit complexity;lower bounds;dynamic programming