MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
    
Yes you are obviously right, I actually got confused with another question I meant to ask instead about P^NP. – Liron Oct 23 '09 at 23:09

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

share|cite|improve this answer
    
See also: en.wikipedia.org/wiki/Polynomial_hierarchy – sdcvvc Oct 23 '09 at 15:24
    
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. – mak Jan 5 at 14:24

Isn't that class NP^NP?

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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