# What do time complexity reductions prove?

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?

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

$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.
• 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}$? – Mirrana 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 If $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)