11
$\begingroup$

Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined as $\textrm{BPP}$ with respect to $\textrm{P}$. More formally we provide polynomially many random bit and we accept an input iff the probability to accept is over $\frac{2}{3}$.

It is known that for non-uniform circuits class we have $\textrm{BPAC}^0=\textrm{AC}^0$:

Miklós Ajtai, Michael Ben-Or: A Theorem on Probabilistic Constant Depth Computations STOC 1984: 471-474

Are generalizations of this theorem known ? For instance, do we know if $\mathrm{BPNC}^1=\mathrm{NC}^1$ (still in the non-uniform setting)? This last question seems somehow non trivial to me since it seems plausible that for instance $s,t\textrm{-Connectivity}$ is in $\textrm{BPNC}^1$.

A relevant post on the subject: https://mathoverflow.net/questions/35184/use-of-randomness-in-constant-parallel-time

Improve this question
$\endgroup$
  • 2
    $\begingroup$ What drives your hunch on connectivity? $\endgroup$ – Michaël Cadilhac Mar 11 '17 at 10:13
  • 4
    $\begingroup$ Are you asking about uniform circuit classes? It’s fairly obvious that nonuniform classes like $\mathrm{NC^1}$ are closed under the BP operator. $\endgroup$ – Emil Jeřábek Mar 11 '17 at 10:46
  • 8
    $\begingroup$ Just use the same argument as for P/poly. You only need the majority function, which is definable in $\mathrm{TC^0\subseteq NC^1}$. (Ajtai and Ben-Or need more work as majority is not available in $\mathrm{AC^0}$.) $\endgroup$ – Emil Jeřábek Mar 11 '17 at 11:45
  • 1
    $\begingroup$ @EmilJeřábek you are perfectly right. For every non-unifom circuit class above $\textrm{TC}^0$ we have $\textrm{BP}-\mathcal{C}=\mathcal{C}$. Thank you very much. $\endgroup$ – C.P. Mar 11 '17 at 16:34
  • 1
    $\begingroup$ @EmilJeřábek: Ah, I see. I think it's borderline; it's obviously not a research question, but it was clearly asked in earnest by someone with some research experience in complexity, who was simply misled by trying to extend Ajtai-Ben-Or rather than using the more straightforward approach. $\endgroup$ – Joshua Grochow Mar 13 '17 at 16:55
10
$\begingroup$

Most nonuniform complexity classes—$\mathrm{NC^1}$ included—are closed under the $\mathrm{BP}$ operator by the same argument as $\mathrm{BPP\subseteq P/poly}$: using the Chernoff–Hoeffding bound, the probability of error can be reduced below $2^{-n}$ by running $O(n)$ instances of the circuit with independent random bits in parallel, and taking a majority vote; then by the union bound, a sequence of random bits gives the correct result for all $2^n$ inputs of length $n$ simultaneously with nonzero probability, and in particular, there exists such a sequence. We can hardwire it into the circuit.

This argument applies to any class of circuits that is closed under taking majority of $O(n)$ parallel copies of a circuit, and fixing input gates to constants. In practice, this means any decent nonuniform class above $\mathrm{TC^0}$, as majority is computable in $\mathrm{TC^0}$.

The proof is more complicated for $\mathrm{AC^0}$, because this class does not compute the majority function. (While I haven’t seen the Ajtai and Ben-Or paper, I’d guess they use some sort of approximate majority.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.