1
$\begingroup$

I have frequently seen two different definitions of polynomial-time reduction. In the following let $A, B \subseteq \Sigma^*$ be decidable problems. I will try to formulate the definitions in my own words:

Definition 1: $A \le_{p_1} B$ iff there exists a polynomial-time computable function $f\colon \Sigma^*\to\Sigma^*$ such that for all $w\in\Sigma^*$:

$$\begin{equation} w\in A \iff f(w) \in B.\tag{1} \end{equation}$$

Definition 2: $A \le_{p_2} B$ iff assuming we have a Turing Machine $M$ which solves $B$, there exists a Turing Machine $M'$ which may call $M$ as a subroutine a polynomial number of times and is also polynominal-time besides of calling $M$, such that the resulting function $f$ defined by $M'$ satisfies $(1)$ for all $w\in\Sigma^*$.

Question 1a: Are these two definitions equivalent? Clearly $\le_{p_1}$ is at least as stronger as $\le_{p_2}$. I would assume it is strictly stronger, because clearly $L^2 \le_{p_2} L$ for any Problem $L$, however I wouldn't assume the assertion holds for $\le_{p_1}$.

Question 1b: What if we restrict our problems to be in $NP$ (and assume $P\neq NP$)? Does that change anything? For the same reason I would assume no.

Question 2: What is the correct definition? I think definition 2 is the correct one which confuses me because most textbooks I have seen use definition 1.

$\endgroup$

1 Answer 1

1
$\begingroup$

Definition 1 is a polynomial-time many-one reduction, also known as a Karp reduction. Definition 2 is a Cook reduction.

NP-completeness is defined with respect to Karp reductions. If you found a textbook that defined NP-complete using Cook reduction, that textbook was wrong, or using a non-standard notion of NP-completeness. I am sympathetic, but the term "NP-complete" has an accepted meaning in the field, and that meaning is based on Karp reductions.

See also https://en.wikipedia.org/wiki/NP-completeness#Completeness_under_different_types_of_reduction, https://cstheory.stackexchange.com/q/138/5038, Can we construct a Karp reduction from a Cook reduction between NP problems?, Teaching NP-completeness - Turing reductions vs Karp reductions, Can one show NP-hardness by Turing reductions?, Graph problem known to be $NP$-complete only under Cook reduction, If you have a Cook reduction in both directions, do you also have a Karp reduction?, https://cstheory.stackexchange.com/q/686/5038, If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete?.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.