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.
9. Define Kolmogorov complexity. Find an upper bound on the Kolmogorov complexity of the string 011011...011 (1000 times).