1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cook's theorem breaks down under some oracle A

  1. Jun 7, 2013 #1
    1. The problem statement, all variables and given/known data
    Demonstrate the existence of an oracle [itex]A[/itex] such that for some [itex]L \in \text{NP}^{\text{A}}[/itex], [itex]L[/itex] does not reduce in polynomial time to [itex]SAT[/itex], the language of satisfiable Boolean formulae, even if the reducing machine has access to oracle [itex]A[/itex].

    2. Relevant equations

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

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

    3. The attempt at a solution

    I'm fairly certain Ladner's theorem relativizes, ie. the same statement holds if we replace [itex]P[/itex], [itex]NP[/itex] in the statement of the theorem with [itex]P^A[/itex], [itex]NP^A[/itex]. We can find an oracle [itex]A[/itex] 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 [itex]L[/itex] such that [itex]L[/itex] cannot be reduced to, in [itex]P^A[/itex] - polynomial time, by any language [itex]L' \in NP^A[/itex].

    The question asks us to find a language that isn't [itex]P^A[/itex]-reducible to [itex]SAT[/itex] .. could we construct some oracle [itex]B[/itex] such that [itex]SAT \in P^B[/itex] but [itex]P^B \neq NP^B[/itex], 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.
     
  2. jcsd
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?



Similar Discussions: Cook's theorem breaks down under some oracle A
Loading...