13
$\begingroup$

Adleman has shown in 1978 that $\mathrm{BPP}\subseteq \mathrm{P/poly}$: if a boolean function $f$ of $n$ variables can be computed by a probabilistic boolean circuit of size $M$, then $f$ can be also computed by a deterministic boolean circuit of size polynomial in $M$ and $n$; actually, of size $O(nM)$.

General Question : Over what other (than boolean) semirings does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold?

To be a bit more specific, a probabilistic circuit $\mathsf{C}$ over a semiring $(S,+,\cdot,0,1)$ uses its "addition" $(+)$ and "multiplication'' $(\cdot)$ operations as gates. Inputs are input variables $x_1,\ldots,x_n$ and possibly some number of additional random variables, which take the values $0$ and $1$ independently with probability $1/2$; here $0$ and $1$ are, respectively, the additive and multiplicative identities of the semiring. Such a circuit $\mathsf{C}$ computes a given function $f:S^n\to S$ if for every $x\in S^n$, $\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$.

The voting function $\mathrm{Maj}(y_1,\ldots,y_m)$ of $m$ variables is a partial function whose value is $y$ if the element $y$ appears more than $m/2$ times among the $y_1,\ldots,y_m$, and is undefined, if no such element $y$ exists. A simple application of Chernoff's and union bounds yields the following.

Majority Trick: If a probabilistic circuit $\mathsf{C}$ computes a function $f:S^n\to S$ on a finite set $X\subseteq S^n$, then there are $m=O(\log|X|)$ realizations $C_1,\ldots,C_m$ of $\mathsf{C}$ such that $f(x)=\mathrm{Maj}(C_1(x),\ldots,C_m(x))$ holds for all $x\in X$.

Over the boolean semiring, the voting function $\mathrm{Maj}$ is the majority function, and has small (even monotone) circuits. So, Adleman's theorem follows by taking $X=\{0,1\}^n$.

But what about other (especially, infinite) semirings? What about the arithmetic semiring $(\mathbb{N},+,\cdot,0,1)$ (with usual addition and multiplication)?

Question 1: Does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold over the arithmetic semiring?

Although I bet for "yes", I cannot show this.

Remark: I am aware of this paper where the authors claim $\mathrm{BPP}\subseteq \mathrm{P/poly}$ over the real field $(\mathbb{R},+,\cdot,0,1)$. They deal with non-monotone arithmetic circuits, and also arrive (in Theorem 4) to circuits with the voting function $\mathrm{Maj}$ as an output gate. But how to simulate this $\mathrm{Maj}$-gate by an arithmetic circuit (be it monotone or not)? I.e. how to get their Corollary 3?

Actually, the following simple argument told to me by Sergey Gashkov (from Moscow University) seems to show that this is impossible (at least for circuits able to compute only polynomials). Suppose we can express $\mathrm{Maj}(x,y,z)$ as a polynomial $f(x,y,z)=ax+by+cz+ h(x,y,z)$. Then $f(x,x,z)=x$ implies $c=0$, $f(x,y,x)=x$ implies $b=0$, and $f(x,y,y)=y$ implies $a=0$. This holds because, over fields of zero characteristic, equality of polynomial-functions means equality of coefficients. Note that in Question 1, the range of probabilistic circuits, and hence, the domain of the $\mathrm{Maj}$-gate is infinite. I therefore have an impression that the linked paper deals only with arithmetic circuits computing functions $f:\mathbb{R}^n\to Y$ with small finite ranges $Y$, like $Y=\{0,1\}$. Then $\mathrm{Maj}:Y^m\to Y$ is indeed easy to compute by an arithmetic circuit. But what if $Y=\mathbb{R}$?

Correction [6.03.2017]: Pascal Koiran (one of the authors of this paper) pointed to me that their model is more powerful than just arithmetic circuits: they allow Sign-gates (outputing $0$ or $1$ depending on whether the input is negative of not). So, the voting function Maj can be simulated in this model, and I take back my "confusion".

In the context of dynamic programming, especially interesting is the same question for tropical min-plus and max-plus semirings $(\mathbb{N}\cup\{+\infty\}, \min, +, +\infty,0)$ and $(\mathbb{N}\cup\{-\infty\}, \max, +, -\infty,0)$.

Question 2: Does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold over tropical semirings?

Held $\mathrm{BPP}\subseteq \mathrm{P/poly}$ in these two semirings, this would mean that randomness cannot speed-up so-called "pure" dynamic programming algorithms! These algorithms only use Min/Max and Sum operations in their recursions; Bellman-Ford, Floyd-Warshall, Held-Karp, and many other prominent DP algorithms are pure.

So far, I can only answer Question 2 (affirmatively) under the one-sided error scenario, when we additionally require $\mathrm{Pr}[\mathsf{C}(x) < f(x)]=0$ over the min-plus semiring (minimization), or $\mathrm{Pr}[\mathsf{C}(x) > f(x)]=0$ over the max-plus semiring (maximization). That is, we now require that the the randomized tropical circuit can never produce any better than optimum value; it can, however, err by giving some worse-than-optimal values. My questions are, however, under the two-sided error scenario.

P.S. [added 27.02.2017]: Here is my attempt to answer Question 1 (affirmatively). The idea is to combine a simplest version of the "combinatorial Nullstellensatz" with an estimate for the Zarankiewicz problem for n-partite hypergraps, due to Erdos and Spencer. Modulo this latter result, the entire argument is elementary.

Note that Question 2 still remains open: the "naive Nullstellensatz" (at least in the form I used) does not hold in tropical semirings.

Improve this question
$\endgroup$
5
  • $\begingroup$ nit: BPP is a uniform class defined using PTMs not circuits. $\endgroup$
    – Kaveh
    Feb 25, 2017 at 21:46
  • $\begingroup$ @Kaveh: yes, in this sense, Adleman's result is even a bit stronger, it holds even for BPP/poly. $\endgroup$
    – Stasys
    Feb 26, 2017 at 9:31
  • $\begingroup$ Don't see how the simple argument shows impossibility... it does seem to show that the coefficients of the x, y, and z monomials must be zero... what am I missing? Also, if a polynomial can't compute Maj, how else can you representing a computation over a semiring? (What else besides a polynomial over the semiring?) Intuitively, over an infinite domain, each constraint on some y (enforcing that on >m/2 y's you must output y) seems "independent" of the others (no subset of constraints implies another) so it seems no "finite" polynomial could satisfy the infinitely many independent constraints. $\endgroup$
    – Ryan Williams
    Feb 27, 2017 at 3:33
  • $\begingroup$ @Ryan: yes, this only shows f=Maj implies h=Maj. But h has degree > 1, so h(x,x,z)=x is impossible. And you are right: circuits over semirings cannot compute anything else as polynomials. So, they cannot compute Maj. But the authors of that paper deal with {+,x,-,/} circuits, with all field operations allowed. Perhaps then Maj can still be somehow computed? (I however, do not see how.) B.t.w. instead of trying to simulate Maj itself, one could answer Q1&Q2 by showing that one Maj-gate cannot substantially decrease circuit size (which is quite plausible). $\endgroup$
    – Stasys
    Feb 27, 2017 at 12:03
  • $\begingroup$ @Ryan: P.S. Igor Sergeev observed that Maj "could" be probable computable over (R,+,x,-,/). E.g. Maj(x,y,z) is computable by f(x,y,z)=(xy+xz-2yz)/(2x-y-z) for all inputs with |{x,y,z}|=2. Note that the simple argument above implies that, already on such inputs, this cannot be done over (R,+,x,-). So, division can help. But we face the division by 0 issue ... $\endgroup$
    – Stasys
    Mar 2, 2017 at 14:20

1 Answer 1

Reset to default
3
$\begingroup$

This is only a partial answer to your general question (I'm not sure what a fully general formulation would be), but it suggests that working over sufficiently nice infinite semirings while constraining the randomness to a finite domain might actually trivialize the question of whether Adleman's theorem holds.

Suppose you're working over the complex numbers $\mathbb{C}$, so that circuits compute polynomials over that field, and suppose the function $f$ is itself computed by some polynomial (however complicated) of the $x$ variables. Then it turns out that already for some fixed $r$, $C(x,r) = f(x)$. The reason is that for each $r$, the set of $x$ with $C(x,r) = f(x)$ determines a Zariski-closed subset of $\mathbb{C}^n$, and so must be all of $\mathbb{C}^n$, or else a subset of measure zero. If all of these sets were to have measure zero, then, because there are only finitely many $r$'s in consideration, the set of $x$ where $\exists r : C(x,r) = f(x)$ would also have measure zero. On the other hand, the assumption that $C$ computes $f$ implies this that set must be all of $\mathbb{C}^n$, so it cannot have measure zero.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting. More generally, a probabilistic circuit of size M is some random variable C taking its values in the set of all circuits (of that type) with at most M gates. [B.t.w. that paper of Cucker at al. allows C be arbitrarily distributed. The "majority trick" stil works.] Can I conclude from your argument that, if the range of C is finite, then Adleman's theorem is trivial when Zarinski-closed subsets are either trivial (sets themselves) or have zero measure? Have we this - "all or nothing" - effect in tropical semirings? (I am mainly interested in them.) $\endgroup$
    – Stasys
    Feb 27, 2017 at 18:24
  • $\begingroup$ I don't know how or whether the argument would generalize to other semirings, sorry. One main thing that's missing (for me) is the geometric intuition akin to how "polynomials that disagree" translates to "measure-zero subsets of $\mathbb{C}^n$". For tropical semirings in particular, the operations seem so different from ordinary polynomials that it's hard to even guess at what the appropriate adaptation ought to be. $\endgroup$
    – Andrew Morgan
    Feb 27, 2017 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.