# NP-Complete

Every other problem in NP must be able to be transformed (in polynomial time) to this problem.

Lies in the intersection between NP-hard and NP.

## Whatâ€™s the point?

- We want to unify all NP Hard problems such that if we solve one of them, we solve the rest as well!

- Provide a framework, for the parts we are unsure about, use wishful thinking and leave it as a hole That way, we can focus on the
*holes*which are the essence of the problem

- We want to solve NP Hard problems in polynomial time

- solve the holes

## How do we prove it?

We are trying to show it lies in the intersection between NP-Hard and NP .

Show it is in NP (show a satisfiable answer can be verified in polynomial time).

Take a known NP-Complete problem, e.g. 3-SAT and reduce it to our problem, L.

If we can do this in polynomial time, all problems can be reduced to L in polynomial time