CSC 341: May 4, 2007

From CSWiki

Jump to: navigation, search

Previous Lecture Next Lecture

[edit]

Instructor's notes for the class session

Today we examine proofs of NP-completeness for six languages: 3SAT, CLIQUE, VERTEX-COVER, HAMPATH, UHAMPATH, and SUBSET-SUM. The first is a minor variation of the proof of the Cook-Levin theorem. In each of the others, we first show that the languages is in NP (usually trivial), and then prove that some language known to be NP-complete can be reduced to the one we're working on. We can then apply Theorem 7.36 to establish the NP-completeness of the reduction target.

Corollary 7.42: 3SAT is NP-complete. The proof is the same as the proof of the Cook-Levin theorem, except that we must extend the preprocessor so that, before releasing a Boolean expression, it is rearranged so as to contain exactly three literals in each clause. A clause with fewer than three literals can be extended by disjoining any literal in the clause one or two more times. A lause with more than three literals can be replaced by several clauses: (a_1 \vee a_2 \vee \ldots \vee a_l) by (a_1 \vee a_2 \vee z_1) \wedge (\neg z_1 \vee a_3 \vee z_2) \wedge \ldots \wedge (\neg z_{l - 3} \vee a_{l - 1} \vee a_l), where z_1, \ldots, z_{l - 3} are new variables. The result of such a replacement is a Boolean expression that has the same value as the original under every assignment of values to the variables that occur in it.

Corollary 7.43: CLIQUE is NP-complete (by Corollary 7.42, Theorem 7.32, and Theorem 7.36).

Theorem 7.44: VERTEX-COVER is NP-complete. The proof is by reduction from 3SAT. Our mapping function must take a 3cnf-formula φ and convert it into a graph G and a number k such that G has a vertex cover of cardinality k if, and only if, φ is satisfiable. Sipser's construction basically shows how to do this in a way that establishes the equivalence of the corresponding problems.

3SAT is polynomial time reducible to HAMPATH, and HAMPATH to UHAMPATH. 3SAT is also polynomial time reducible to SUBSET-SUM. The problems at the end of the chapter provide several more instances of problems that can be shown to be NP-complete. Paul E. Dunne of the University of Liverpool provides a more extensive compilation (lacking proofs).

[edit]

Study questions

  1. The INDEPENDENT-SET problem is the language containing all encodings \langle G, k\rangle such that G is a graph, k is a positive integer, and there are k or more vertices in G that are not connected to one another by edges. Prove that INDEPENDENT-SET is NP-complete.
  2. Is the set of NP-complete languages closed under complementation? under union? Justify your answers.
[edit]

Proposed Solutions


    1. Any NP-complete language must be a member of NP. INDEPENDENT-SET can be solved in NP time, because all that is necessary is to nondeterministically choose k vertices that are a subset of G and check for edges between them.
    2. To show that INDEPENDENT-SET is NP-complete, show that 3SAT is polynomial time reducible to it. The problem is very similar to the CLIQUE reduction problem in Theorem 7.32. Use the same method to convert φ to a graph as is used in the CLIQUE problem. Instead of looking for a k-clique within the graph, look for a k sized independent set. If such a set exists, then the clause is false.
  2. NP-complete languages are closed under complementation, because we can reduce an NP-complete problem to its complement, simply by reversing the output values of the decider. Assuming I'm correct about that part, NP-complete languages are not closed under union, because for a NP-complete language A, we can decide members of A \cup \bar{A} in constant time.

Previous Lecture Next Lecture

Front Door

Retrieved from "http://wiki.cs.grinnell.edu/mediawiki/index.php/CSC_341:_May_4%2C_2007"
Personal tools