0
$\begingroup$

While reading Sipser, in computability I read about many to one mapping reducibility and Turing reducibility,the latter one being a more general form of reducibility. But in the introductory chapter about complexity, where the book shows examples of NP-Complete problems,the polynomial reductions used are only many to one mapping reductions. So in polynomial reductions is there a general form of reductions? For example the author first proves that 3-SAT is NP-Complete and then for clique problem,subset sum problem,vertex cover problem and Hamiltonian path problem he reduces 3-SAT to the respective problems. The reductions used are many to one mapping reductions. Are general Turing reductions used while proving NP-Completeness of a problem ?

$\endgroup$
3
  • 1
    $\begingroup$ Take a look at en.wikipedia.org/wiki/Reduction_%28complexity%29 and en.wikipedia.org/wiki/Turing_reduction. Turing reductions / Cook reductions are a very general kind of reduction. Can you be more precise about what you are asking? $\endgroup$
    – D.W.
    Jan 18, 2016 at 6:21
  • $\begingroup$ I am also unclear about what the quesiton is (community votes?). Are you asking if there are more general notions of reduction? Why yes, clearly; you get them by dropping any of the restrictions. Are you asking if there is a general technique to find reductions? Not quite, but there are patterns you can use. $\endgroup$
    – Raphael
    Jan 18, 2016 at 7:53
  • 1
    $\begingroup$ With the edit, this has now become a duplicate of cs.stackexchange.com/q/9556/755. The answer is: no, we don't use Turing reductions while proving NP-completeness, because NP-completeness is defined in terms of many-one reductions, not Turing reductions. You might also be interested in cs.stackexchange.com/q/16386/755 andhttp://cstheory.stackexchange.com/q/686/5038 and en.wikipedia.org/wiki/…. $\endgroup$
    – D.W.
    Jan 18, 2016 at 8:00

0