0
$\begingroup$

This question already has an answer here:

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$

marked as duplicate by D.W. Jan 18 '16 at 8:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.