Name

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

9. Define Kolmogorov complexity. Find an upper bound on the Kolmogorov complexity of the string 011011...011 (1000 times).