CS 5315, Test 2, Spring 2007

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:

8-9. Describe how to compute the product of two n by n matrices in parallel. 10. Describe a possible physical scheme that would enable us to solve NP-hard problems in polynomial time. For extra credit: describe two such schemes.

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.