Timeline for Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$
Current License: CC BY-SA 3.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18, 2017 at 18:11 | answer | added | Tayfun Pay | timeline score: 4 | |
| Sep 10, 2014 at 18:35 | history | edited | Giorgio Camerani | CC BY-SA 3.0 |
added 7 characters in body
|
| Sep 10, 2014 at 3:05 | comment | added | Sasho Nikolov | 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 (eccc.hpi-web.de/report/1998/055/comment/1/download) | |
| Sep 9, 2014 at 23:16 | comment | added | Lev Reyzin♦ | I think this discussion needs to be taken to our chat room. | |
| Sep 9, 2014 at 22:49 | comment | added | Giorgio Camerani | 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}$? | |
| Sep 9, 2014 at 22:42 | comment | added | Giorgio Camerani | ... 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). | |
| Sep 9, 2014 at 22:33 | comment | added | Giorgio Camerani | ... 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... | |
| Sep 9, 2014 at 22:16 | comment | added | Giorgio Camerani | 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... | |
| Sep 9, 2014 at 21:57 | comment | added | Giorgio Camerani | @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? | |
| Sep 9, 2014 at 5:30 | comment | added | Sasho Nikolov | 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. | |
| Sep 9, 2014 at 0:36 | comment | added | mdxn | @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). | |
| Sep 8, 2014 at 21:07 | comment | added | Giorgio Camerani | @EmilJeřábek That's the point: such reasoning is similar to mine, you were attacking a 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. | |
| Sep 8, 2014 at 17:34 | comment | added | Emil Jeřábek | 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. | |
| Sep 8, 2014 at 16:58 | comment | added | Giorgio Camerani | @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). | |
| Sep 8, 2014 at 16:44 | comment | added | Giorgio Camerani | @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". | |
| Sep 8, 2014 at 16:29 | comment | added | Giorgio Camerani | @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". | |
| Sep 8, 2014 at 15:44 | comment | added | Emil Jeřábek | (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.) | |
| Sep 8, 2014 at 15:39 | comment | added | Emil Jeřábek | 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$. | |
| Sep 8, 2014 at 15:31 | comment | added | Giorgio Camerani | ... 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}$. | |
| Sep 8, 2014 at 15:30 | comment | added | Giorgio Camerani | @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}$... | |
| Sep 8, 2014 at 15:05 | history | edited | Giorgio Camerani | CC BY-SA 3.0 |
added 93 characters in body
|
| Sep 8, 2014 at 14:46 | comment | added | Emil Jeřábek | 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 . | |
| Sep 8, 2014 at 14:20 | comment | added | Giorgio Camerani | @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? | |
| Sep 8, 2014 at 14:00 | comment | added | Emil Jeřábek | 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. | |
| Sep 8, 2014 at 13:45 | history | edited | Giorgio Camerani | CC BY-SA 3.0 |
Enriched 1st question by adding a known consequence
|
| Sep 7, 2014 at 23:45 | history | tweeted | twitter.com/#!/StackCSTheory/status/508762914052780032 | ||
| Sep 7, 2014 at 19:08 | history | edited | Giorgio Camerani | CC BY-SA 3.0 |
edited title
|
| Sep 7, 2014 at 13:46 | history | edited | Giorgio Camerani | CC BY-SA 3.0 |
added 8 characters in body
|
| Sep 7, 2014 at 5:21 | history | edited | Giorgio Camerani | CC BY-SA 3.0 |
added 3 characters in body
|
| Sep 6, 2014 at 19:54 | comment | added | Giorgio Camerani | @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... | |
| Sep 6, 2014 at 15:35 | comment | added | Emil Jeřábek | $\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 cstheory.stackexchange.com/questions/3887). | |
| Sep 6, 2014 at 14:22 | history | asked | Giorgio Camerani | CC BY-SA 3.0 |