# Karp's reduction strategy

One way to prove that a problem $$X$$ is NP-Complete is to pick two NP-Complete problems $$Z$$ and $$W$$ and show that ($$\leq_p$$ is polynomial reduction): $$\begin{array}{rr}X \leq_p Z & (1)\\W \leq_p X&(2)\end{array}$$

The usual way to prove NP-Completeness however, is to follow Karp’s strategy which consists in proving that $$\begin{array}{rr}X\in \textsf{NP} & (3)\\W \leq_p X&(4)\end{array}$$

I am trying to show that $$(1)$$ and $$(3)$$ are equivalents, but but I'm not sure where I can start. Can someone help me with how to do this?

• HINT: What's the definition of "NP-complete"? If $X$ is in NP and $Z$ is NP-complete, can you compare $X$ and $Z$? – Noah Schweber May 6 at 15:30

## 1 Answer

$$(3)\Rightarrow (1)$$ should just be a consequence of the definition of $$\textsf{NP}$$-completeness.

For $$(1)\Rightarrow (3)$$, you can use the fact that there exists a function $$f$$, computable in polynomial time, such that $$u\in X \Leftrightarrow f(u) \in Z$$. Now to decide if $$u\in X$$, you can compute $$f(u)$$, and then decide nondeterministically if $$f(u)\in Z$$.