Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
Surely this class, being $\text{NP}^\text{NP}$, is by definition equal to $\Sigma_2^p$. In particular, if the Polynomial Hierarchy (PH) does not collapse, then it does not contain $\Pi_2^p$.
-
$\begingroup$ Yes you are obviously right, I actually got confused with another question I meant to ask instead about P^NP. $\endgroup$– LironCommented Oct 23, 2009 at 23:09
$\begingroup$
$\endgroup$
2
Yes, NP^SAT = NP^NP, because SAT is complete for NP. I don't know what else can be said about this class (it's not in the complexity zoo). See the wikipedia oracle page for more details.
By the way, the above "computer" tag is not very relevant, it should rather be "complexity", or "complexity-theory".
-
$\begingroup$ See also: en.wikipedia.org/wiki/Polynomial_hierarchy $\endgroup$– sdcvvcCommented Oct 23, 2009 at 15:24
-
$\begingroup$ NP^NP actually is in the complexity zoo under its alternative name Sigma_2^p: complexityzoo.uwaterloo.ca/Complexity_Zoo:S#sigma2p There are some complete problems given there. $\endgroup$– makCommented Jan 5, 2016 at 14:24
$\begingroup$
$\endgroup$
Isn't that class NP^NP?
