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 ?
$\begingroup$
$\endgroup$
3
asked Jan 18, 2016 at 6:12
-
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. ♦Commented 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$– RaphaelCommented 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. ♦Commented Jan 18, 2016 at 8:00
Add a comment
|