9 - Karp Reductions and NP-completeness

• every problem in NP can be expressed/reduced to an instance of 3-SAT
• Karp reducibility : generlization of the notion of reducing to an instance of 3-SAT.
• Karp-reducibility

  A) polynomial-time

  B) every

  
• The polynomial-time function f maps elements from L to elements of L' and elements from complement L to complement L'.

  using an algorithm taking as input f(x) which returns 1 iff $f(x) \in L'$which is th case iff $x \in L$

  
• The main objective behind reductions is to express a given language by means of another language which is at least as hard as the original language .
• Clique : given an undirected graph G and a positive integer C, does G contain a subset of size C consisting of mutaually adjacent nodes ?

  
• P membership


  Let L, L' in {0,1}* be two languages. If L $L \leq_p L'$and $L' \in P$then $L \in P$
• Transitivity of Karp reductions

  if $L \leq_p L'$and $L' \leq L''$then $L \leq L''$
• We say that L' is NP-hard if $L \leq_q L'$for every $L \in NP$. We say that L' is NP-complete if $L' \in NP$and L' is NP-hard
• 3-SAT is NP-complete
• Clique is NP-complete
• Method for proving NP-completenes

  1. Show that Q in NP
  2. Choose some problem P known to be NP-hard. Provide a function f transforming any instance of P into an instance of Q such that x in P iff f(x) in Q
• P = NP iff 3-SAT in P