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?

  1. We want to unify all NP Hard problems such that if we solve one of them, we solve the rest as well!
  1. 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
  1. We want to solve NP Hard problems in polynomial time
  1. solve the holes

How do we prove it?

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

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

  2. 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

logo