# NP-Complete

A problem $X∈NP$ is $NP$-complete if $Y≤_{P}X$ for all $Y∈NP$.

- where $≤_{P}$ is a Polynomial Time Reduction

Alternative (similar definition): A problem $X$ is **NP-complete** if $X∈NP$ and $X$ is NP-Hard.

Informally

Informally, we say a problem is NP-complete if it is the hardest problem in NP.

From CS241E: If a problem is NP-complete, then a polynomial time algorithm solving that problem could be modified to solve all other NP-complete problems in polynomial time.

Some NP-Complete Problems:

Implications

To prove that a problem $X∈NP$ is $NP$-complete, we just need to find a NP-Complete problem $Y$, and prove that $Y≤_{P}X$.

- For instance, prove that $3-SAT≤_{P}X$

The definition feels a little cyclical

We’re essentially proving that a problem is NP-complete if it can be reduced to another NP-complete problem.

However, proving it without the cyclical part is doable. But it’s a lot longer.