patternMinor
Is QMA known to contain Co-NP?
Viewed 0 times
containqmaknown
Problem
Is QMA known to contain Co-NP?
If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
Solution
This is not currently known. In my MSc. thesis, I show that, if it were true, then a consequence would be that $NP^{NP}\subseteq QMA$ (Theorem 21, below). I conjecture that in fact $coNP\subseteq
QMA$ implies $PH\subseteq QMA$, but I was not able to prove that.
Lemma 14. $NP^{QMA\cap coQMA}\subseteq QMA$.
Theorem 21. If $QMA$ contains $co\text-NP$, then $NP^{NP}\subseteq QMA$
Proof. If $QMA$ contains $coNP$, then, equivalently, $NP\subseteq coQMA$, so we have $NP\subseteq QMA\cap coQMA$. Plugging this in, we get $NP^{NP}\subseteq NP^{QMA\cap coQMA}\subseteq QMA$. $\square$
The thesis contains other consequences, and variations and generalizations of this theorem.
QMA$ implies $PH\subseteq QMA$, but I was not able to prove that.
Lemma 14. $NP^{QMA\cap coQMA}\subseteq QMA$.
Theorem 21. If $QMA$ contains $co\text-NP$, then $NP^{NP}\subseteq QMA$
Proof. If $QMA$ contains $coNP$, then, equivalently, $NP\subseteq coQMA$, so we have $NP\subseteq QMA\cap coQMA$. Plugging this in, we get $NP^{NP}\subseteq NP^{QMA\cap coQMA}\subseteq QMA$. $\square$
The thesis contains other consequences, and variations and generalizations of this theorem.
Context
StackExchange Computer Science Q#128509, answer score: 4
Revisions (0)
No revisions yet.