**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.
- 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).