12

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.
Giorgio Camerani
  • 6,842
  • 1
  • 34
  • 64
  • 22
    $\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 Sep 06 '14 at 15:35
  • 7
    @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 Sep 06 '14 at 19:54
  • 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 Sep 08 '14 at 14:00
  • 1
    @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 Sep 08 '14 at 14:20
  • 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 . – Emil Jeřábek Sep 08 '14 at 14:46
  • 2
    @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 Sep 08 '14 at 15:30
  • ... 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 Sep 08 '14 at 15:31
  • 9
    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 Sep 08 '14 at 15:39
  • (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 Sep 08 '14 at 15:44
  • 1
    @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 Sep 08 '14 at 16:29
  • 1
    @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 Sep 08 '14 at 16:44
  • @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 Sep 08 '14 at 16:58
  • 3
    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 Sep 08 '14 at 17:34
  • 2
    @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. – Giorgio Camerani Sep 08 '14 at 21:07
  • 4
    @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 Sep 09 '14 at 00:36
  • 4
    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 Sep 09 '14 at 05:30
  • @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 Sep 09 '14 at 21:57
  • 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 Sep 09 '14 at 22:16
  • ... 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 Sep 09 '14 at 22:33
  • ... 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 Sep 09 '14 at 22:42
  • 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 Sep 09 '14 at 22:49
  • 4
    I think this discussion needs to be taken to our chat room. – Lev Reyzin Sep 09 '14 at 23:16
  • 8
    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 Sep 10 '14 at 03:05

1 Answers1

4

There are two oracle sets defined in T88 such that ${\bf NP^A \not \subseteq \oplus P ^A}$ and ${\bf \oplus P^B \not \subseteq NP^B}$.

Tayfun Pay
  • 2,598
  • 2
  • 18
  • 45