NP COMPLETE PROBLEMS

What is NP-Complete?
Informally, these are the hardest problems in
the class NP.
If any NP-complete problem can be solved by a
polynomial time deterministic algorithm, then
every problem in NP can be solved by a
polynomial time deterministic algorithm
But no polynomial time deterministic algorithm
is known to solve any of them.

Examples of NP-complete problems
• Traveling salesman problem
• Hamiltonian cycle problem
• Clique problem
• Subset sum problem
• Boolean satisfiability problem
• Many thousands of other important
computational problems in computer science,
mathematics, economics, manufacturing,
communications, etc.

SAT (Boolean satisfiability)
In order to use polynomial-time reductions to show
that problems are NP-complete, we must be able to
directly show that at least one problem is NPcomplete,
without using a polynomial-time reduction
Cook proved that the the Boolean satisfiability
problem (denoted SAT) is NP-complete. He did not
use a polynomial-time reduction to prove this.
This was the first problem proved to be NP-complete.