CSC 320 Spring 2012

Assignment #5

Due: At the beginning of class on April 5 (last day of class).

• From the book: 5.7.1. NOTE: Some older versions of the book have a missing state in the second configuration. The state should be h, the halt state.

• From the book: 5.7.4.(a).

• Post correspondence systems were introduced briefly in the "fun" lecture on Thur. They also occur in problem 5.5.2.

  (a) Show that the following Post correspondence system has a solution: (1,0,010,11) and (10,10,01,1).

  (b) Show that the following Post correspondence system does not have a solution: (10,011,101) and (101,11,011).

  To think about: Why is it semidecidable whether a Post correspodence system has a solution or not?

• From the book: 6.2.4 but for the Independent Set Problem (pg 283).

• From the book: 7.3.4.(a),(b),(c).

• Prove that the following two problems are NP-complete.

  INPUT: Positive integers x₁, x₂, ... x_n, M, C
  OUTPUT: Can the numbers be partitioned into at most C subsets such that the sum of the numbers in each subset is at most M?

  INPUT: A CNF boolean expression B.
  OUTPUT: Does B have at least 4 distinct satisfying assignments?