# A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

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?

• 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. – Yuval Filmus Jul 11 '14 at 4:58

• 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. – Yuval Filmus Jul 11 '14 at 12:14