<p>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 <a href="http://dx.doi.org/10.1137/0210008" rel="noreferrer">Bennett and Gill</a>, 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).</p>

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

<p>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&gt;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}$.</p>

CC BY-SA 3.0
2017-11-01T17:12:33.973Z
2017-11-01T17:12:33.973Z
Emil Jeřábek
<p>I'm pretty sure this has a trivial answer but it's always faster to ask the community :-)</p>

<p>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.</p>

<p>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."</p>

<p>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.</p>

<p>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.</p>

<p>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?</p>

<p>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$".</p>

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

CC BY-SA 3.0
2017-11-01T13:02:46.623Z
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
CC BY-SA 3.0
2017-11-01T13:13:08.493Z
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
CC BY-SA 3.0
2017-11-01T13:25:36.507Z
Thanks. I edited the last part of the question to fix the non-computability issue. I'd assume that both are true statements. But the complexity zoo claims that Almost-P=BPP, citing a paper that shows a different statement "relative to a random oracle, P=BPP". And with the given definition, I don't see how that result can be modified to show Almost-P=BPP. In particular, how do you prove $\text{Almost-P} \subseteq \mathrm{BPP}$?
Mahdi Cheraghchi
CC BY-SA 3.0
2017-11-01T13:29:19.420Z
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
CC BY-SA 3.0
2017-11-01T13:34:42.893Z
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
CC BY-SA 3.0
2017-11-01T13:46:50.047Z
@EmilJeřábek: Seems like your comments make an answer..
Joshua Grochow
<complexity-classes><relativization><random-oracles>
Almost-P and related definitions
Mahdi Cheraghchi
# Almost-P and related definitions

(Asked by: username_0 on 2017-11-01)

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?

**Tags:** complexity-classes, relativization, random-oracles
> **Comments:**
> **username_1**: 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).  
> **username_1**: 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.  
> **username_0**: Thanks. I edited the last part of the question to fix the non-computability issue. I'd assume that both are true statements. But the complexity zoo claims that Almost-P=BPP, citing a paper that shows a different statement "relative to a random oracle, P=BPP". And with the given definition, I don't see how that result can be modified to show Almost-P=BPP. In particular, how do you prove $\text{Almost-P} \subseteq \mathrm{BPP}$?  
> **username_1**: 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.)  
> **username_1**: 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$.  
> **username_2**: @EmilJeřábek: Seems like your comments make an answer..  

---

## 1 answers

### Answer by username_1 on 2017-11-01. Score: 8 | Accepted answer

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](http://dx.doi.org/10.1137/0210008), 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}$.


---

