12
$\begingroup$

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.
Improve this question
$\endgroup$
23
  • 22
    $\begingroup$ $\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). $\endgroup$
    – Emil Jeřábek
    Commented Sep 6, 2014 at 15:35
  • 7
    $\begingroup$ @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... $\endgroup$
    – Giorgio Camerani
    Commented Sep 6, 2014 at 19:54
  • 9
    $\begingroup$ 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$. $\endgroup$
    – Emil Jeřábek
    Commented Sep 8, 2014 at 15:39
  • 4
    $\begingroup$ @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). $\endgroup$
    – mdxn
    Commented Sep 9, 2014 at 0:36
  • 8
    $\begingroup$ 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) $\endgroup$
    – Sasho Nikolov
    Commented Sep 10, 2014 at 3:05

1 Answer 1

Reset to default
4
$\begingroup$

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}$.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.