World's most popular travel blog for travel bloggers.

[Solved]: A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

, , No Comments
Problem Detail: 

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?

Asked By : vzn

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback