I'm pretty sure this has a trivial answer but it's always faster to ask the community :-)

I understand that, relative to a random oracle, P=BPP. But this is sometimes phrased via the shorthand "Almost-P=BPP", which I find rather confusing.

Complexity zoo defines Almost-P as "The class of problems that are in $P^A$ with probability 1, where A is an oracle chosen uniformly at random."

Logically, L belonging to Almost-P would then mean that: With probability 1 over a random instantiation of an oracle tape A, there is a polynomial time Turing machine T(A) that decides L.

Now, the poor BPP machine trying to decide L would have no idea which T(A) to simulate. The choice of T(A) may wildly vary depending on A.

Should Almost-P (similarly, Almost-anything) be rather defined as the set of languages L for which there is a polynomial time Turing machine T with an oracle tape such that, with probability 1 over the instantiation of the oracle tape, the language decided by T ends up being L?

Under neither of the above definitions does the statement BPP=Almost-P seems to be logically equivalent to "relative to a random oracle A, $P^A=BPP^A$".

My question is now, what is the precise definition of the class Almost-P (or, for that matter, Almost-anything)? And/or, what am I missing above?

  • 1
    $\begingroup$ The given definition of Almost-P is correct. The fact that it equals BPP is a nontrivial fact, using the Lebesgue density theorem. This implies “relative to a random oracle $A$, $\mathrm{BPP\subseteq P}^A$”, but it does not imply “$\mathrm P^A=\mathrm{BPP}^A=\mathrm{BPP}$”. In fact, the latter is false with probability 1, as $\mathrm P^A$ includes $A$ itself, which is with probability 1 not in BPP (indeed, not computable). $\endgroup$ Nov 1 '17 at 13:02
  • 1
    $\begingroup$ So, “Almost-P = BPP” and “for a random oracle $A$, $\mathrm P^A=\mathrm{BPP}^A$” are both true results, but different. One is not a “rephrasing” of the other. $\endgroup$ Nov 1 '17 at 13:13
  • 2
    $\begingroup$ The Bennett–Gill paper proves many results, and in particular, it proves the two results in question. That does not make them “equivalent”. (Well, they state Almost-P = BPP as a corollary, without using the “Almost-P” notation, and without a full proof, but anyway.) $\endgroup$ Nov 1 '17 at 13:29
  • 5
    $\begingroup$ The proof of the less obvious inclusion goes as follows. Let $L$ be in Almost-P. Since there are only countably many Turing machines, there is a single poly-time oracle machine $M^A$ such that $M^A$ computes $L$ with probability $\epsilon>0$. By the Lebesgue density theorem, there exists a finite prefix $a$ such that relative to oracles $A$ extending $a$, $M^A$ computes $L$ with probability $\ge3/4$. One can hardwire $a$ into the machine, and use a supply of random bits to simulate the remaining part of the oracle to obtain a BPP machine for $L$. $\endgroup$ Nov 1 '17 at 13:34
  • 1
    $\begingroup$ @EmilJeřábek: Seems like your comments make an answer.. $\endgroup$ Nov 1 '17 at 13:46

The question seems to be predicated on a misunderstanding: the statements “relative to a random oracle $A$, $\mathrm{P}^A=\mathrm{BPP}^A$” and “$\mathrm{Almost\text-P}=\mathrm{BPP}$” are not meant to be rephrasings of each other. The complexity zoo refers to a paper of Bennett and Gill, which proves the former statement (and many other things) in detail, but it also separately claims the second statement (though they do not use the $\mathrm{Almost\text-P}$ notation, and do not really give a proof).

The definition of $\mathrm{Almost\text-P}$ in the zoo is correct.

The proof of $\mathrm{Almost\text-P\subseteq BPP}$ goes as follows. Let $L\in\mathrm{Almost\text-P}$. Since there are only countably many Turing machines, there exists an oracle polynomial-time Turing machine $M$ such that $M^A$ computes $L$ with positive probability $\epsilon>0$. Using the Lebesgue density theorem, there exists a finite oracle prefix $A_0$ such that relative to random oracles $A$ that extend $A_0$, $M^A$ computes $L$ with probability $\ge3/4$. We can hardwire $A_0$ into the Turing machine, and simulate access to the rest of the oracle by random coin flips to obtain a randomized poly-time machine for $L$ with probability of success $\ge3/4$. Thus, $L\in\mathrm{BPP}$.


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.