Is $P^{SAT}$ equal to NP $\cup$ co-NP?

1.9k Views Asked by At

I have following problem: Is $P$ with a $SAT$ oracle equal to $NP \cup coNP$ assuming that $NP \neq co-NP \neq P $?

I can show that $NP \subseteq P^{SAT}$ and $coNP \subseteq P^{SAT}$. But it is much harder to prove or to contradict it the other way.

Do you have any hints?

1

There are 1 best solutions below

2
On

${\rm P}^{\rm SAT}$ is usually written ${\rm P}^{\rm NP}$ because an oracle for any NP-complete problem gives the same complexity class.

It's conjectured (but not known) that ${\rm NP} \cup {\rm coNP} ⊊ {\rm P}^{\rm NP}$: see Lutz and Mayordomo (1996), so you shouldn't expect proving or disproving it to be easy!

${\rm P}^{\rm NP}$ is also known as $\Delta^P_2$ — it's a complexity class in the second level of the polynomial hierarchy: $$ {\rm P} ⊆ {\rm NP} ⊆ {\rm P}^{\rm NP} ⊆ {\rm NP}^{\rm NP} ⊆ {\rm P}^{{\rm NP}^{\rm NP}} ⊆ \dotsb. $$ It's conjectured that all these classes are distinct.