# Is there a general form of polynomial reductions in complexity theory? [duplicate]

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 ?

• 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?
– D.W.
Commented Jan 18, 2016 at 6:21
• 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. Commented Jan 18, 2016 at 7:53
• 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/….
– D.W.
Commented Jan 18, 2016 at 8:00