1
$\begingroup$

Luca Trevisan wrote, " The oracle $C$ tells us that we cannot have a relativizing proof that derives the $𝑁𝑃 ⊈ 𝑃/π‘π‘œπ‘™π‘¦$ conclusion from the $𝑃 ≠𝑁𝑃$ assumption, so a theorem such as Karp-Lipton, which derives (via relativizing arguments) the $𝑁𝑃 ⊈ 𝑃/π‘π‘œπ‘™π‘¦$ conclusion from a stronger assumption, is about as much as we can hope to prove using relativizing arguments. – " This is replied to the question that "The fact there exists $C$ s.t. $P^C β‰  NP^C$, but $NP^C \subset P/poly^C$ ... what does this give us?".

He wrote that Karp-Lipton theorem is proved by relativizing arguments. How do we know that this theorem is derived from relativizing arguments? I remember the proof and it has nothing about relativizing (I don't want to sketch the proof here since it takes some time and you can find it in Arora and Barak's textbook).

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ A proof is relativizing if it works just as well in the presence of an oracle. This is not something you notice unless you look for it. $\endgroup$
    – Yuval Filmus
    May 17, 2021 at 19:44
  • $\begingroup$ Thank you Yuval. This brings the question: how do you know if it works well in the presence of an oracle? Do I need to try all oracles to see whether it works well as in the real world? $\endgroup$
    – user777
    May 17, 2021 at 20:41
  • 2
    $\begingroup$ You need to carefully go over the proof and check that it still goes through even in the presence of an oracle. You definitely don’t β€œtry all oracles”. A relativizing proof still works in the presence of an arbitrary oracle. $\endgroup$
    – Yuval Filmus
    May 17, 2021 at 20:43
  • $\begingroup$ Thank you Yuval for this note. First, we have two facts that every diagonalization technique will use, these are (1) TM is represented by binary strings and (2) TM can be simulated by another in short time (let's say polynomial in the size of the input). Since Karp-Lipton theorem is used self-reducibility of SAT in the proof and self-reducibility is based on algorithms (algorithms means TM) then the results relativize. Note that I use the fact that diagonalization is relativize. $\endgroup$
    – user777
    May 21, 2021 at 5:11

0

Reset to default

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.