Are these two definitions of an NP-Complete problem equivalent?

user_19365770 0
Viewed 42

Definition 1 (usual definition) A problem B is NP-Complete if

  • B is in NP
  • For C in NP, C is polynomal-time reducible to B

Definition 2 (in a few documents) A problem B is NP-Complete if

  • B is in NP
  • if B admits a polynomial-time algorithm, then all problems in NP also admit a polynomial-time algorithm

(as in "On the Inherent Intractability of Certain Coding Problems,..., Berlekamp, McEliece and Tilborg" and other documents

np np-complete algorithm
1 Answers

Definition 1 is the definition of NP-completeness you get if you define reducibility to be polynomial-time mapping reducibility (sometimes called polynomial-time many-one reducibility). That is, you’re allowed to reduce one problem to another by doing polynomial work to transform the input, then make a single call to the target problem. This is the standard definition of NP-completeness.

Definition 2 is the (nonstandard) definition of NP-completeness you get if you use polynomial-time Turing reducibility (called Cook reductions), in which you are allowed to spend polynomial time including an arbitrary number of calls to an oracle (solver) for the problem you’re reducing to.

user_5015570
Related