|
2 |
edited tags
|
||
|
|
1 |
|
||
Characterize P^NPWhat can you say about the complexity class P^NP, i.e. decision problems solvable by a polytime TM with an oracle for SAT? Obviously P^NP is in PH somewhere between NP union coNP, and Sigma2 intersect Pi2. What else is known about that complexity class?
|
||||
