# Almost-P and related definitions

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?

• 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). – Emil Jeřábek Nov 1 '17 at 13:02
• 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. – Emil Jeřábek Nov 1 '17 at 13:13
• 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.) – Emil Jeřábek Nov 1 '17 at 13:29
• 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$. – Emil Jeřábek Nov 1 '17 at 13:34
• @EmilJeřábek: Seems like your comments make an answer.. – Joshua Grochow 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}$.