Due: At the beginning of class on April 5 (last day of class).
(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?
INPUT: Positive integers x1, x2, ... xn, 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?