Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?
Obviously it contains Sigma2 union Pi2, but what else?
|
3 | deleted 58 characters in body | ||
|
|
||||
|
|
2 | deleted 76 characters in body; edited tags; edited title | ||
Characterize How can one characterize NP^SAT?Can you help me understand the class of problems solvable by a nondetermimistic Turing machin machine with an oracle for SAT running in poly polynomial 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.
|
||||
|
|
1 |
|
||
Characterize NP^SATCan 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.
|
||||
