2
$\begingroup$

I may have missed something in my classes - but with $A\leq_{P}B$... Does this show that, if $A\in \textbf{NP-Complete}$, that $B\in \textbf{NP}$ or $B\in \textbf{NP-Complete}$?

Or maybe I got things backwards. If $A$ is polynomial-time-reducable to $B$, and $B$ is $\textbf{NP}$-complete, does that make $A$ $\textbf{NP}$ or $\textbf{NP}$-complete?

$\endgroup$
  • $\begingroup$ What does the definition of $\leq_p$ say? $\endgroup$ – Raphael Feb 14 '13 at 6:51
4
$\begingroup$

$A \leq_p B$ denotes that you can reduce $A$ to $B$ in polynomial time. That is, you can always transform an instance of $A$ to an instance of $B$ and you do this in polynomial time. Now if you have a polynomial time algorithm for solving an instance of $B$, you also have a polynomial time algorithm for solving an instance of $A$, clearly.

To show that $C$ is $\mathsf{NP}$-complete, you need two conditions to hold. First, $C$ must be in $\mathsf{NP}$. Second, every problem in $\mathsf{NP}$ is reducible to $C$ in polynomial time.

$\endgroup$
  • $\begingroup$ Let me rephrase that... I think I misunderstood the order of things here. If $A$ is polynomial time reducable to $B$, and $B$ is $\textbf{NP}$-complete, does that make $A$ $\textbf{NP}$-complete as well, or just in $\textbf{NP}$? $\endgroup$ – Mirrana Feb 13 '13 at 23:59
  • 3
    $\begingroup$ @agent154 In that case $A$ is NP-hard (the second condition holds). If you can show that $A$ is also in NP, then you have shown $A$ is NP-complete as well. $\endgroup$ – Juho Feb 14 '13 at 0:07
4
$\begingroup$

enter image description hereIf $A\leq_{P}B$ and $A\in \textbf{NP-Complete}$, then $B\in \textbf{NP}-Hard$. $NP-Hard$ is a class of problems that are "at least as hard as the hardest problems in NP". (Image is from Wikipedia)

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