CS 5315, Test 2, Spring 2009

Name

(Please do not forget to put your name on all extra sheets of paper)

1. Suppose that we want to find a solution to the propositional satisfiability problem. Is it possible, given a program that is known to always halt, to check whether this program always provides a correct solution? If it is possible, describe an algorithm. If it is not possible, provide a proof. In this and other problems, a brief description of the proof is sufficient. Hint: everything can be coded in integers.

2. Define what is P, what is NP, what is NP-hard, and what is NP-complete. Hint: no need to give an exact definition of reduction.

3. Estimate Kolmogorov complexity of a string 20092009 ... 2009 (repeated 1,000,000 times).

4. Use the general algorithm for transforming propositional expressions into DNF and CNF forms to transform a Boolean expression if (x1 \/ x2) then (-x1) into DNF and CNF forms. Explain where this transformation is used in the proof that computational satisfiability is NP-hard.

5-8. Reduce the satisfiability problem for the formula (-x1 \/ -x2) & (x1 \/ x2 \/ -x3) to:

• 3-coloring
• clique
• subset sum problem
• interval computations

9. Prove that the 5-coloring problem is NP-hard. You can use the fact that 3-coloring is NP-hard.

10-11. Describe how to compute the product of two n by n matrices in parallel.

• Does this problem belong to the class NC? explain your answer.