NP Problem

NP-Complete

A problem $X\in NP$ is $NP$-complete if $Y{\le }_{P}X$ for all $Y\in NP$.

• where ${\le }_P$ is a Polynomial Time Reduction

Alternative (similar definition): A problem $X$ is NP-complete if $X\in 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:

• 3-SAT, SAT
• Subset Sum
• Hamiltonian Path, Hamiltonian Cycle
• 0/1 Knapsack
• Clique Problem
  • Maximum Clique
  • Maximum Independent Set
  • Minimum Vertex Cover

Implications

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

• For instance, prove that $\text{3-SAT}{\le }_{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.

Related

• NP-Hard
• P vs. NP