NP-complete

Definition

A problem $Y\in NP$ with the property that for every problem $X\in NP$, $X{\le }_{P}Y$.

NP-complete problem is at least as hard as NP problem.

Prove problem $Y$ is $NP-complete$

1. Show that Y is NP There exists at least one criteria that can solve problem Y in polynomial time. The problem is NP as given a solution, we only need to check …
2. Choose an NP-complete problem $X$
3. Prove that $X{\le }_{P}Y$

Known NP-complete problems

1. 3-SAT Problem
2. Vertex Cover Problem
3. Set Cover Problem
4. Independent Set Problem
5. Partition Problem
6. 3-Dimensional Matching
7. Exact Cover by 3-Sets
8. Hamiltonian Cycle
9. TSP