CS 5315, Test 2, Spring 2006


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

1. An "n!-checker" is, by definition, a program which checks whether a given program p always correctly computes the factorial n! for a given input n. Prove that n!-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*x1 into DNF and CNF forms.

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

8-9. Describe how to compute the sum 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.