**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.
- Is NC a subset of P? explain your answer.
- Is NC equal to P? Explain the relationship between this equation and linear programming problems. Give an example of a linear programming problem.
- What will be the computation time if we take communication time into consideration? Where is a related argument used in the proof that satisfiability is NP-hard?

13. Describe a possible physical scheme that would enable us to solve NP-hard problems in polynomial time.