**Name**

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

1. Is it possible, given a program and a data, to check whether a given program halts on the given data? If it is possible, describe an algorithm. If it is not possible, provide a proof. In this and other problems, a brief description of the proof is sufficient.

2. Is it possible, given a program that always halts, to check whether this program always produces a correct result? If it is possible, describe an algorithm. If it is not possible, provide a proof.

3. Is the union of two recursively enumerable (r.e.) sets always r.e.? If your answer is "yes", prove it. If your answer is "no", provide a counterexample.

4. Is the intersection of two r.e. sets always r.e.? If your answer is "yes", prove it. If your answer is "no", provide a counterexample.

5. Is the complement to a r.e. set always r.e.? If your answer is "yes", prove it. If your answer is "no", provide a counterexample.

6. Use the general algorithm for transforming propositional
expressions into DNF and CNF forms to transform a Boolean
expression *x1+0.1*x2<0.3+5*x2* into DNF and CNF forms.
Explain where this transformation is used in the proof that
computational satisfiability is NP-hard.

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

- 3-coloring
- clique
- subset sum problem
- interval computations

10-11. Describe how to compute the sum 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?