Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
Surely this class, being NP^NP, is by definition equal to Sigma2. In particular, if PH does not collapse, then it does not contain Pi2. 


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 "complexitytheory". 


Isn't that class NP^NP? 

