Polynomial-Time Reducible

#Computers
To show a problem is NP complete (not easy), you may show that a known NP complete problem reduces into the given problem

$\displaystyle Y\leq _p X\land Y\text{ is NP complete}\rightarrow Y\text{ is NP complete}$

• Reads that if $\displaystyle Y$ is polynomial reducible/transformable to $\displaystyle X$ and $\displaystyle Y$ is NP complete, then Y must be NP complete
• Proof by contradiction:
  • Assume $\displaystyle Y$ isn't NP complete with the above givens
  • Then we could solve $\displaystyle X$ in polynomial time by solving $\displaystyle Y$ and then reducing it to $\displaystyle X$, which contradicts the fact that $\displaystyle X$ is NP complete