Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
What does the definition of $\leq_p$ say? – Raphael Feb 14 '13 at 6:51
up vote 4 down vote accepted

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

share|cite|improve this answer
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}$? – agent154 Feb 13 '13 at 23:59
@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. – Juho Feb 14 '13 at 0:07

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)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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