Name

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?