# Cook's theorem breaks down under some oracle A

1. Jun 7, 2013

### meiji11

1. The problem statement, all variables and given/known data
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$.

2. Relevant 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$.

3. 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.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted