CS 5315, Test 2, Tuesday, April 26, 2005

Name

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

1. An "(n+5)-checker" is, by definition, a program which checks whether a given program p always correctly computes n+5 for a given input n. Prove that (n+5)-checkers do not exist.

2. Let A be an arbitrary oracle. Prove that the union of two sets which are r.e. with respect to this oracle is also r.e. with respect to A.

3. Define what it means for a problem to be from the class P, from the class NP, to be NP-hard. Give example of two general problems about which we have proved NP-hardness. (No proof is needed.) For extra credit: prove that the main problem of interval computations is NP-hard.

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

5. Assuming that 3-coloring is NP-hard, prove that 4-coloring is NP-hard.

6. Use the OR-gadget from the book (that we used in the class) to prove that the corresponding graph can be colored in 3 colors if and only if a \/ b is true. For extra credit: use the extended OR-gadget to prove that the corresponding graph can be colored in 3 colors if and only if a \/ b \/ c is true.

7-8. 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.