2
$\begingroup$

Wikipedia states on sparse languages that

There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP $\subseteq$ P/poly.

Is that correct in that it is so far proven for an arbitrary Turing reduction and not a limited P-time reduction? (Could it be true for P-time reductions also, but maybe not proven so far?) It cites this without reference. What is a reference for this?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ We know unconditionally that there is an unrestricted Turing reduction from SAT (or indeed, any computable language) to any non-trivial sparse language; there is even an unrestricted Karp reduction. That's why the Wikipedia article shouldn't be interpreted in this way. $\endgroup$ – Yuval Filmus Jul 11 '14 at 4:58
3
$\begingroup$

No, what you suggest would be meaningless. The Turing reduction is also polytime. For a proof, see Theorem 3.2 in Oded Goldreich's lecture notes.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ it is not really my "suggestion"... so the wikipedia writeup is not strictly correct as it stands. ps does anyone know if Mahaney's thm is in a textbook? $\endgroup$ – vzn Jul 11 '14 at 4:39
  • 1
    $\begingroup$ No, it is strictly correct. In the context it is clear that polytime reductions are meant. General Karp reductions also don't have time constraints, yet in the context (Mahaney's theorem) it is clear that polytime reductions are meant. In other words, all reductions mentioned are polytime. General reductions don't make much sense in the context of complexity theory. $\endgroup$ – Yuval Filmus Jul 11 '14 at 4:56
  • $\begingroup$ whatever. the useful writeup you give (thx) is apparently for Karp reductions. so still not following the wikipedia writeup. is wikipedia actually referring to a Cook reduction? but who/where is the Cook reduction case proven if it is different (as wikipedia seems to be unclearly asserting)? $\endgroup$ – vzn Jul 11 '14 at 5:03
  • 2
    $\begingroup$ The reduction in Theorem 3.2 is a polytime Turing reduction ($\leq^p_T$), which is the same as a polytime Cook reduction; Cook reductions and Turing reductions are the same. Polytime Karp reductions ($\leq^p_m$) appear in Theorem 4.1. $\endgroup$ – Yuval Filmus Jul 11 '14 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.