0
$\begingroup$

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?

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

$(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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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