**Name**

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

1. A "cube-checker" is, by definition, a program which checks
whether a given program *p* always correctly computes the cube
*n*^3 for a given input *n*. Prove that cube-checkers do
not exist.

2. Define what it means for a problem to be from the class P, from the class NP, to be NP-hard.

3. Use a general algorithm to transform a Boolean expression
*x1+0.1*x2<0.2+5*x2* into DNF and CNF forms.

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

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

- 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?

11. What is Kolmogorov complexity? Estimate the Kolmogorov
complexity of a string 001001...001001 (2,007 times). *For extra
credit:* prove that Kolmogorov complexity is not computable.