Cook's theorem breaks down under some oracle A

[meiji11]

Homework Statement

Demonstrate the existence of an oracle $A$ such that for some $L \in \text{NP}^{\text{A}}$, $L$ does not reduce in polynomial time to $SAT$, the language of satisfiable Boolean formulae, even if the reducing machine has access to oracle $A$.

Homework Equations

Ladner's theorem states that, given $P \neq NP$, there exists a language $L \in NP /\ P$ such that $L$ is not NP-complete.

Another result, by Baker-Gill-Solovay, is that there exist oracles A, B such that $P^A = NP^A$ and $P^B \neq NP^B$.

The Attempt at a Solution

I'm fairly certain Ladner's theorem relativizes, ie. the same statement holds if we replace $P$, $NP$ in the statement of the theorem with $P^A$, $NP^A$. We can find an oracle $A$ for which the two aren't equal by Baker-Gill-Solovay. All Ladner's theorem gives, at that point, is the fact that there exists some $L$ such that $L$ cannot be reduced to, in $P^A$ - polynomial time, by any language $L' \in NP^A$.

The question asks us to find a language that isn't $P^A$-reducible to $SAT$ .. could we construct some oracle $B$ such that $SAT \in P^B$ but $P^B \neq NP^B$, because that would clearly do it.. how, though? The constructions of such oracles have been very contrived. I'm convinced that isn't the right way to go, but can't think of anything else.

 

[KataKoniK]

Hello there,

Thank you for your post. You are correct in your approach - we can use Ladner's theorem to show the existence of an oracle A such that for some L \in NP^A, L does not reduce in polynomial time to SAT, even with access to oracle A.

To construct such an oracle A, we can use the Baker-Gill-Solovay result. Let B be an oracle such that P^B = NP^B and P^A \neq NP^A. Now, we can define A to be the oracle that answers queries to B in the following way:

1. If the query is of the form "Is x \in SAT?", A answers "yes" if x \in P^B and "no" if x \notin P^B.
2. If the query is of the form "Is x \in L?", A answers "yes" if x \in P^A and "no" if x \notin P^A.

By construction, we have that SAT \in P^B and P^B \neq NP^B. This means that A cannot reduce SAT to any language L' \in NP^A in polynomial time, even with access to A. Therefore, we have found an oracle A that satisfies the desired conditions.

I hope this helps. Let me know if you have any further questions.