Welcome to MathOverflow

Question

0

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

edited Oct 23 2009 at 23:17

asked Oct 23 2009 at 6:29

Liron
99●6

Martin Orr · Accepted Answer · 2009-10-23 16:22:26Z UTC

3

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.

answered Oct 23 2009 at 16:22

Martin Orr
726●3●11

Yes you are obviously right, I actually got confused with another question I meant to ask instead about P^NP. – Liron Oct 23 2009 at 23:09

subshift · Answer 2 · 2009-10-23 08:35:19Z UTC

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

Mensen · Answer 3 · 2009-10-23 07:59:58Z UTC

0

Isn't that class NP^NP?

answered Oct 23 2009 at 7:59

Mensen
490●3●11

How can one characterize NP^SAT?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.