Skip to main content
1 of 3
Liron
  • 213
  • 2
  • 9

Characterize NP^SAT

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

Obviously it contains Sigma2 union Pi2, but what else?

Btw someone should create a Complexity tag; I can't do it since I'm a new user.

Liron
  • 213
  • 2
  • 9