NP-Complete

• NP: verifiable in polynomial time
  • If a decision problem is hard, the optimization is no easier.
  • Reduction
• Prove NP-hard: find another NP-hard problem, and create polynomial conversion back and forth
• Abstract problems
  • Set of instances $I$ and set of solutions $S$, encoding $e:I\to \{0,1{\}}^{\ast }$.
• Cook’s theorem
  • The satisfiability (SAT) is NP-Complete.
  • Given a boolean expression, find assignment of values to variables, so that the expression has value of 1
• CNF = Conjunctive Normal Form, each clause has at most 3 terms.
• k-clique problem
  • k-clique is in NP (easy, done)
  • k-clique is in NP-hard
• Create $G=(V,E)$ as follows
  • For each appearance of a variable in Expression as a vertex
  • For vertices which form complements of a variable, no edge connects them
  • Connect all other pairs of vertices by edges

---

$G^{\prime }=G$, $d=k$,