<p>There are two oracle sets defined in <a href="https://scholar.google.com/citations?view_op=view_citation&amp;hl=en&amp;user=9tCatQwAAAAJ&amp;citation_for_view=9tCatQwAAAAJ:IjCSPb-OGe4C" rel="nofollow noreferrer">T88</a> such that <span class="math-container">${\bf NP^A \not \subseteq \oplus P ^A}$</span> and <span class="math-container">${\bf \oplus P^B \not \subseteq NP^B}$</span>.</p>

CC BY-SA 4.0
2017-06-18T18:11:06.257Z
2019-12-25T16:41:45.980Z
2019-12-25T16:41:45.980Z
Tayfun Pay
<p>I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER to SAT.</p>

<p>Given a cubic graph $G$, the reduction outputs a CNF formula $F$ having both the following properties:</p>

<ul>
<li>$F$ has at most $1$ satisfying assignment.</li>
<li>$F$ is satisfiable if and only if the number of vertex covers of $G$ is odd.</li>
</ul>

<blockquote>
  <p><strong>Questions</strong></p>
  
  <ol>
  <li>Which would be the consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? A consequence which I'm already aware of is the following: $\mathbf{PH}$ would be reducible to $\mathbf{NP}$ via two-sided randomized reduction. In other words we would have $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ (using Toda's Theorem, which states that $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$, by merely replacing $\oplus\mathbf{P}$ with $\mathbf{NP}$). I do not know if $\mathbf{BPP}^{\mathbf{NP}}$ has been shown to be contained in some level $i$ of the Polynomial Hierarchy: if yes, a further consequence would be that $\mathbf{PH}$ collapses to such level $i$. <s>Moreover, under widely accepted derandomization assumptions ($\mathbf{BPP} = \mathbf{P}$), the Polynomial Hierarchy would collapse between the first and the second level, as we would have $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$ (I'm told this is not true, however I will not erase this line until I fully understand why).</s></li>
  <li>If I'm not mistaken, the aforementioned reduction would actually prove more than $\oplus \mathbf{P} \subseteq \mathbf{NP}$. It would prove $\oplus \mathbf{P} \subseteq \mathbf{UP}$. Which would be the consequences of $\oplus \mathbf{P} \subseteq \mathbf{UP}$, <strong>in addition</strong> to those already implied by $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? I do not know exactly whether $\oplus \mathbf{P} \subseteq \mathbf{UP}$ would add more surprise to the already surprising consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$, nor to what extent. Intuitively I presume it would, and to a pretty wide extent.</li>
  </ol>
</blockquote>

CC BY-SA 3.0
2014-09-06T15:35:27.210Z
$\oplus\mathrm P$ is closed under complement, and the randomized reduction of PH to $\oplus\mathrm P$ is many-one, hence $\oplus\mathrm P\subseteq\mathrm{NP}$ actually implies $\mathrm{PH}=\Sigma^P_2=\Pi^P_2=\mathrm{AM}\cap\mathrm{coAM}$, and $\mathrm{PH}\subseteq\mathrm{NP/poly}\cap\mathrm{coNP/poly}$. UP doesn’t make much difference (cf. the lack of anything useful in http://cstheory.stackexchange.com/questions/3887).
Emil Jeřábek
CC BY-SA 3.0
2014-09-06T19:54:20.223Z
@EmilJeřábek Thanks for your interesting comment, I did not know that consequences. I knew the question you pointed me to, however I would have expected $\oplus \mathbf{P}\subseteq\mathbf{UP}$ (as well as $\mathbf{NP}\subseteq\mathbf{UP}$) to be surprising, at least because $\mathbf{UP}$ is not known to have complete problems. It is interesting how something widely conjectured to be false ($\mathbf{NP}\subseteq\mathbf{UP}$) is not known to have, if true, any shocking consequence. You might consider to expand your comment into an answer...
Giorgio Camerani
CC BY-SA 3.0
2014-09-08T14:00:06.167Z
BPP = P does not imply $\mathrm{BPP^{NP}}=\mathrm{P^{NP}}$. On the other hand, AM = NP is a widely believed derandomization assumption on its own.
Emil Jeřábek
CC BY-SA 3.0
2014-09-08T14:20:03.143Z
@EmilJeřábek I'm certain you're right, but I fail to understand why. Why, if $\mathbf{BPP} \subseteq \mathbf{P}$, cannot I conclude $\mathbf{BPP}^\mathbf{NP} \subseteq \mathbf{P}^\mathbf{NP}$? If the machine to which I attach the oracle is at least as powerful, why should not the inclusion follow?
Giorgio Camerani
CC BY-SA 3.0
2014-09-08T14:46:50.980Z
Because $\mathrm{BPP}\subseteq\mathrm{P}$ is a statement about languages, not about (oracle) machines. You can’t attach oracles to languages. These are elementary questions that would be better suited for cs.stackexchange.com .
Emil Jeřábek
CC BY-SA 3.0
2014-09-08T15:30:41.853Z
@EmilJeřábek Firstly, you can just ignore my questions if you consider them too elementary. Secondly, $\mathbf{BPP} = \mathbf{P}$ **certainly** implies that the following sentence is true: _"The set of languages recognized by a $\mathbf{BPP}$ machine with a $\mathbf{NP}$ oracle is equal to the set of languages recognized by a $\mathbf{P}$ machine with a $\mathbf{NP}$ oracle"_. I condensed such sentence in the equation $\mathbf{BPP}^\mathbf{NP}=\mathbf{P}^\mathbf{NP}$...
Giorgio Camerani
CC BY-SA 3.0
2014-09-08T15:31:54.620Z
... maybe mine was an abuse of notation, in which case I'm curious to know what you instead mean by $\mathbf{BPP}^\mathbf{NP}=\mathbf{P}^\mathbf{NP}$.
Giorgio Camerani
CC BY-SA 3.0
2014-09-08T15:39:43.613Z
No, you are completely wrong. BPP = P only says that every language that is computable by a BPP machine is also computable by a P machine. It does not say anything whatsoever about languages that are computable by a BPP machine with a nontrivial oracle. By your faulty argument, NP = P implies $\mathrm{NP}^A=\mathrm P^A$ for every $A$, which we know to be false, hence $\mathrm{NP}\ne\mathrm P$ is solved. And for that matter, your argument would imply $\mathrm{BPP}\ne\mathrm P$, as there exist oracles $A$ for which $\mathrm{BPP}^A\ne\mathrm P^A$.
Emil Jeřábek
CC BY-SA 3.0
2014-09-08T15:44:05.383Z
(I’m ignoring the additional problem that there is no such thing as a BPP machine, as BPP is a semantic class. This only makes it worse.)
Emil Jeřábek
CC BY-SA 3.0
2014-09-08T16:29:20.380Z
@EmilJeřábek As for your first comment: you misunderstood me, by performing an undue generalization of my sentence. I have never mentioned a generic oracle $A$. I've only mentioned a $\mathbf{NP}$ oracle. Can you prove me wrong when I say $\mathbf{BPP} = \mathbf{P} \Rightarrow \mathbf{BPP}^\mathbf{NP} = \mathbf{P}^\mathbf{NP}$? If you can, prove me wrong, otherwise you should say _"is not known to imply"_ rather than _"does not imply"_.
Giorgio Camerani
CC BY-SA 3.0
2014-09-08T16:44:20.417Z
@EmilJeřábek As for your second comment: you can just equate _"$\mathbf{BPP}$ machine"_ with _"an efficient algorithm which makes access to a genuine random-number source"_.
Giorgio Camerani
CC BY-SA 3.0
2014-09-08T16:58:57.197Z
@EmilJeřábek Addendum to my before-last comment: not only I've just mentioned a $\mathbf{NP}$ oracle (instead of a generic oracle $A$), I've also applied it only to $\mathbf{BPP}$ and $\mathbf{P}$ (instead of to any pair of complexity classes, as your $\mathbf{NP}^A = \mathbf{P}^A$ example seems to allege).
Giorgio Camerani
CC BY-SA 3.0
2014-09-08T17:34:54.070Z
I was trying to be helpful by giving examples where similar reasoning as yours to absurd results. If your reaction to that is to point out trivial details in which these examples differ from the actual situation at hand, I really can’t help you, and my good faith is quickly running out. So, only one thing: *you* are the one who is claiming that P = BPP implies something, so the onus is on *you* to prove it, not on others to prove the opposite.
Emil Jeřábek
CC BY-SA 3.0
2014-09-08T21:07:43.160Z
@EmilJeřábek That's the point: such reasoning is _similar_ to mine, you were [attacking a straw man](http://en.wikipedia.org/wiki/Straw_man). Those _"trivial"_ details completely adulterate what I've actually said, twisting it from something very specific into something too general. I would say that the onus is on both: on me, because I've said that $\mathbf{BPP} = \mathbf{P}$ _does_ imply something, and on you, because you said that $\mathbf{BPP} = \mathbf{P}$ _does not_ imply something.
Giorgio Camerani
CC BY-SA 3.0
2014-09-09T00:36:35.387Z
@Giorgio: He's only claiming that the line of reasoning you considered does not work in this circumstance. Relevant portion: "If the machine to which I attach the oracle is at least as powerful, why should not the inclusion follow?". He does not appear to say that the claim itself is false; just that your particular intuition doesn't work. We can't yet rule out that probabilistic aspects of the PPTM couldn't get more benefit from that oracle. The probabilistic TM has more tools at its disposal, but the tool might not provide strict benefit without additional ones (such as the NP oracle).
mdxn
CC BY-SA 3.0
2014-09-09T05:30:14.987Z
Emil cannot prove the implication you are claiming is wrong unless he can show BPP is equal to P (because any implication is true when the assumption is false). So you may take his comment to mean that the implication is not known to be true, and that **most certainly** your reasoning is wrong.
Sasho Nikolov
CC BY-SA 3.0
2014-09-09T21:57:46.523Z
@SashoNikolov Yes I know that any implication is true when the assumption is false, and thus I know that, in order to prove my implication wrong, Emil should firstly prove that $\mathbf{BPP}=\mathbf{P}$. But I'm not sure I understand what you actually meant with the rest of your comment: are you claiming that, as soon as $\mathbf{BPP}=\mathbf{P}$ is proved, $\mathbf{BPP}^\mathbf{NP}=\mathbf{P}^\mathbf{NP}$ is instantaneously shown to be false without any further effort?
Giorgio Camerani
CC BY-SA 3.0
2014-09-09T22:16:10.357Z
Thanks for your comment, I believe that this thread of comments has been infected by 2 misunderstandings between myself and Emil:  
1) Firstly, I was talking only about the very specific case of $\mathbf{BPP}$ and $\mathbf{P}$, both equipped with a $\mathbf{NP}$ oracle, but I gave the impression of being talking much more generally (I recognize that the sentence you cited gives such impression).  
2) Secondly, I've reasoned under an (unproven) assumption that I did not even state (my fault), wrongly believing that it would have been implicitly shared by Emil and others...
Giorgio Camerani
CC BY-SA 3.0
2014-09-09T22:33:15.343Z
... More precisely, when I said _"is at least as powerful"_, what I actually had in mind was _"can be simulated by"_. Emil correctly parsed _"is at least as powerful"_ as _"recognizes the same set of languages"_, which is the right way it should be parsed. The assumption under which I've reasoned is the following: in order to prove $\mathbf{BPP} = \mathbf{P}$, one can either a) furnish a deterministic polynomial time algorithm for some $\mathbf{BPP}$-complete problem, or b) prove the existence of a good-enough (as in Andy Yao's paper) pseudorandom number generator...
Giorgio Camerani
CC BY-SA 3.0
2014-09-09T22:42:02.793Z
... as strategy a) seems out of reach, since $\mathbf{BPP}$ is not known to have complete problems (but will have if $\mathbf{BPP} = \mathbf{P}$), the only viable option seems strategy b) (I'm aware of further results relating the $\mathbf{BPP} = \mathbf{P}$ question to circuit lower bounds, however, if I'm not mistaken, after all they are related to the existence of good-enough pseudorandom number generators). To summarize, my unstated and unproven assumption was that $\mathbf{BPP}=\mathbf{P}$ will be proven by using strategy b).
Giorgio Camerani
CC BY-SA 3.0
2014-09-09T22:49:23.823Z
Clearly this will not necessarily be the case (however I would bet on it). Now, to conclude, if this will be indeed the case, then shouldn't we become able, by using such PRNG, to simulate any $\mathbf{BPP}$ computation with a $\mathbf{P}$ machine, therefore implying $\mathbf{BPP}^\mathbf{NP} = \mathbf{P}^\mathbf{NP}$?
Giorgio Camerani
CC BY-SA 3.0
2014-09-09T23:16:49.350Z
I think this discussion needs to be taken to our chat room.
Lev Reyzin
CC BY-SA 3.0
2014-09-10T03:05:25.380Z
Even with the assumption that a PRNG strong enough to collapse P and BPP exists, I do not see why this must necessarily imply BPP with an NP oracle and P with an NP oracle must be the same. Normally PRNGs have the guarantee that no polysize circuit can distinguish their output from truly random bits. But for the oracle machines you need the guarantee for every polysize circuit with NP gates allowed, and this is stronger. Impagliazzo-Wigderson does relativize, but you need to strengthen the hardness assumption (http://eccc.hpi-web.de/report/1998/055/comment/1/download/)
Sasho Nikolov
<cc.complexity-theory><graph-theory><complexity-classes><sat><counting-complexity>
Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$
Giorgio Camerani
# Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

(Asked by: username_0 on 2014-09-06)

I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER to SAT.

Given a cubic graph $G$, the reduction outputs a CNF formula $F$ having both the following properties:

* $F$ has at most $1$ satisfying assignment.
* $F$ is satisfiable if and only if the number of vertex covers of $G$ is odd.

> **Questions**
>
> 1. Which would be the consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? A consequence which I'm already aware of is the following: $\mathbf{PH}$ would be reducible to $\mathbf{NP}$ via two-sided randomized reduction. In other words we would have $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ (using Toda's Theorem, which states that $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$, by merely replacing $\oplus\mathbf{P}$ with $\mathbf{NP}$). I do not know if $\mathbf{BPP}^{\mathbf{NP}}$ has been shown to be contained in some level $i$ of the Polynomial Hierarchy: if yes, a further consequence would be that $\mathbf{PH}$ collapses to such level $i$. ~~Moreover, under widely accepted derandomization assumptions ($\mathbf{BPP} = \mathbf{P}$), the Polynomial Hierarchy would collapse between the first and the second level, as we would have $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta\_2^\mathbf{P}$ (I'm told this is not true, however I will not erase this line until I fully understand why).~~
> 2. If I'm not mistaken, the aforementioned reduction would actually prove more than $\oplus \mathbf{P} \subseteq \mathbf{NP}$. It would prove $\oplus \mathbf{P} \subseteq \mathbf{UP}$. Which would be the consequences of $\oplus \mathbf{P} \subseteq \mathbf{UP}$, **in addition** to those already implied by $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? I do not know exactly whether $\oplus \mathbf{P} \subseteq \mathbf{UP}$ would add more surprise to the already surprising consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$, nor to what extent. Intuitively I presume it would, and to a pretty wide extent.

**Tags:** cc.complexity-theory, graph-theory, complexity-classes, sat, counting-complexity

> **Comments:**
> **username_1**: $\oplus\mathrm P$ is closed under complement, and the randomized reduction of PH to $\oplus\mathrm P$ is many-one, hence $\oplus\mathrm P\subseteq\mathrm{NP}$ actually implies $\mathrm{PH}=\Sigma^P_2=\Pi^P_2=\mathrm{AM}\cap\mathrm{coAM}$, and $\mathrm{PH}\subseteq\mathrm{NP/poly}\cap\mathrm{coNP/poly}$. UP doesn’t make much difference (cf. the lack of anything useful in http://cstheory.stackexchange.com/questions/3887).  
> **username_0**: @EmilJeřábek Thanks for your interesting comment, I did not know that consequences. I knew the question you pointed me to, however I would have expected $\oplus \mathbf{P}\subseteq\mathbf{UP}$ (as well as $\mathbf{NP}\subseteq\mathbf{UP}$) to be surprising, at least because $\mathbf{UP}$ is not known to have complete problems. It is interesting how something widely conjectured to be false ($\mathbf{NP}\subseteq\mathbf{UP}$) is not known to have, if true, any shocking consequence. You might consider to expand your comment into an answer...  
> **username_1**: BPP = P does not imply $\mathrm{BPP^{NP}}=\mathrm{P^{NP}}$. On the other hand, AM = NP is a widely believed derandomization assumption on its own.  
> **username_0**: @EmilJeřábek I'm certain you're right, but I fail to understand why. Why, if $\mathbf{BPP} \subseteq \mathbf{P}$, cannot I conclude $\mathbf{BPP}^\mathbf{NP} \subseteq \mathbf{P}^\mathbf{NP}$? If the machine to which I attach the oracle is at least as powerful, why should not the inclusion follow?  
> **username_1**: Because $\mathrm{BPP}\subseteq\mathrm{P}$ is a statement about languages, not about (oracle) machines. You can’t attach oracles to languages. These are elementary questions that would be better suited for cs.stackexchange.com .  
> **username_0**: @EmilJeřábek Firstly, you can just ignore my questions if you consider them too elementary. Secondly, $\mathbf{BPP} = \mathbf{P}$ **certainly** implies that the following sentence is true: _"The set of languages recognized by a $\mathbf{BPP}$ machine with a $\mathbf{NP}$ oracle is equal to the set of languages recognized by a $\mathbf{P}$ machine with a $\mathbf{NP}$ oracle"_. I condensed such sentence in the equation $\mathbf{BPP}^\mathbf{NP}=\mathbf{P}^\mathbf{NP}$...  
> **username_0**: ... maybe mine was an abuse of notation, in which case I'm curious to know what you instead mean by $\mathbf{BPP}^\mathbf{NP}=\mathbf{P}^\mathbf{NP}$.  
> **username_1**: No, you are completely wrong. BPP = P only says that every language that is computable by a BPP machine is also computable by a P machine. It does not say anything whatsoever about languages that are computable by a BPP machine with a nontrivial oracle. By your faulty argument, NP = P implies $\mathrm{NP}^A=\mathrm P^A$ for every $A$, which we know to be false, hence $\mathrm{NP}\ne\mathrm P$ is solved. And for that matter, your argument would imply $\mathrm{BPP}\ne\mathrm P$, as there exist oracles $A$ for which $\mathrm{BPP}^A\ne\mathrm P^A$.  
> **username_1**: (I’m ignoring the additional problem that there is no such thing as a BPP machine, as BPP is a semantic class. This only makes it worse.)  
> **username_0**: @EmilJeřábek As for your first comment: you misunderstood me, by performing an undue generalization of my sentence. I have never mentioned a generic oracle $A$. I've only mentioned a $\mathbf{NP}$ oracle. Can you prove me wrong when I say $\mathbf{BPP} = \mathbf{P} \Rightarrow \mathbf{BPP}^\mathbf{NP} = \mathbf{P}^\mathbf{NP}$? If you can, prove me wrong, otherwise you should say _"is not known to imply"_ rather than _"does not imply"_.  
> **username_0**: @EmilJeřábek As for your second comment: you can just equate _"$\mathbf{BPP}$ machine"_ with _"an efficient algorithm which makes access to a genuine random-number source"_.  
> **username_0**: @EmilJeřábek Addendum to my before-last comment: not only I've just mentioned a $\mathbf{NP}$ oracle (instead of a generic oracle $A$), I've also applied it only to $\mathbf{BPP}$ and $\mathbf{P}$ (instead of to any pair of complexity classes, as your $\mathbf{NP}^A = \mathbf{P}^A$ example seems to allege).  
> **username_1**: I was trying to be helpful by giving examples where similar reasoning as yours to absurd results. If your reaction to that is to point out trivial details in which these examples differ from the actual situation at hand, I really can’t help you, and my good faith is quickly running out. So, only one thing: *you* are the one who is claiming that P = BPP implies something, so the onus is on *you* to prove it, not on others to prove the opposite.  
> **username_0**: @EmilJeřábek That's the point: such reasoning is _similar_ to mine, you were [attacking a straw man](http://en.wikipedia.org/wiki/Straw_man). Those _"trivial"_ details completely adulterate what I've actually said, twisting it from something very specific into something too general. I would say that the onus is on both: on me, because I've said that $\mathbf{BPP} = \mathbf{P}$ _does_ imply something, and on you, because you said that $\mathbf{BPP} = \mathbf{P}$ _does not_ imply something.  
> **username_2**: @Giorgio: He's only claiming that the line of reasoning you considered does not work in this circumstance. Relevant portion: "If the machine to which I attach the oracle is at least as powerful, why should not the inclusion follow?". He does not appear to say that the claim itself is false; just that your particular intuition doesn't work. We can't yet rule out that probabilistic aspects of the PPTM couldn't get more benefit from that oracle. The probabilistic TM has more tools at its disposal, but the tool might not provide strict benefit without additional ones (such as the NP oracle).  
> **username_3**: Emil cannot prove the implication you are claiming is wrong unless he can show BPP is equal to P (because any implication is true when the assumption is false). So you may take his comment to mean that the implication is not known to be true, and that **most certainly** your reasoning is wrong.  
> **username_0**: @SashoNikolov Yes I know that any implication is true when the assumption is false, and thus I know that, in order to prove my implication wrong, Emil should firstly prove that $\mathbf{BPP}=\mathbf{P}$. But I'm not sure I understand what you actually meant with the rest of your comment: are you claiming that, as soon as $\mathbf{BPP}=\mathbf{P}$ is proved, $\mathbf{BPP}^\mathbf{NP}=\mathbf{P}^\mathbf{NP}$ is instantaneously shown to be false without any further effort?  
> **username_0**: Thanks for your comment, I believe that this thread of comments has been infected by 2 misunderstandings between myself and Emil:   1) Firstly, I was talking only about the very specific case of $\mathbf{BPP}$ and $\mathbf{P}$, both equipped with a $\mathbf{NP}$ oracle, but I gave the impression of being talking much more generally (I recognize that the sentence you cited gives such impression).   2) Secondly, I've reasoned under an (unproven) assumption that I did not even state (my fault), wrongly believing that it would have been implicitly shared by Emil and others...  
> **username_0**: ... More precisely, when I said _"is at least as powerful"_, what I actually had in mind was _"can be simulated by"_. Emil correctly parsed _"is at least as powerful"_ as _"recognizes the same set of languages"_, which is the right way it should be parsed. The assumption under which I've reasoned is the following: in order to prove $\mathbf{BPP} = \mathbf{P}$, one can either a) furnish a deterministic polynomial time algorithm for some $\mathbf{BPP}$-complete problem, or b) prove the existence of a good-enough (as in Andy Yao's paper) pseudorandom number generator...  
> **username_0**: ... as strategy a) seems out of reach, since $\mathbf{BPP}$ is not known to have complete problems (but will have if $\mathbf{BPP} = \mathbf{P}$), the only viable option seems strategy b) (I'm aware of further results relating the $\mathbf{BPP} = \mathbf{P}$ question to circuit lower bounds, however, if I'm not mistaken, after all they are related to the existence of good-enough pseudorandom number generators). To summarize, my unstated and unproven assumption was that $\mathbf{BPP}=\mathbf{P}$ will be proven by using strategy b).  
> **username_0**: Clearly this will not necessarily be the case (however I would bet on it). Now, to conclude, if this will be indeed the case, then shouldn't we become able, by using such PRNG, to simulate any $\mathbf{BPP}$ computation with a $\mathbf{P}$ machine, therefore implying $\mathbf{BPP}^\mathbf{NP} = \mathbf{P}^\mathbf{NP}$?  
> **username_4**: I think this discussion needs to be taken to our chat room.  
> **username_3**: Even with the assumption that a PRNG strong enough to collapse P and BPP exists, I do not see why this must necessarily imply BPP with an NP oracle and P with an NP oracle must be the same. Normally PRNGs have the guarantee that no polysize circuit can distinguish their output from truly random bits. But for the oracle machines you need the guarantee for every polysize circuit with NP gates allowed, and this is stronger. Impagliazzo-Wigderson does relativize, but you need to strengthen the hardness assumption (http://eccc.hpi-web.de/report/1998/055/comment/1/download/)  

---

## 1 answers

### Answer by username_5 on 2017-06-18. Score: 4

There are two oracle sets defined in [T88](https://scholar.google.com/citations?view_op=view_citation&hl=en&user=9tCatQwAAAAJ&citation_for_view=9tCatQwAAAAJ:IjCSPb-OGe4C) such that ${\bf NP^A \not \subseteq \oplus P ^A}$ and ${\bf \oplus P^B \not \subseteq NP^B}$.


---

