CS 5315, Test 2, Spring 2006
Name
(Please do not forget to put your name on all extra sheets of
paper)
1. An "n!-checker" is, by definition, a program which checks
whether a given program p
always correctly computes the factorial n!
for a given input n.
Prove that n!-checkers do not exist.
2. Define what it means for a problem to be from the class
P, from the class NP, to be NP-hard.
3. Use a general algorithm to transform a Boolean
expression x1-0.1*x2<0.2-5*x1 into DNF and CNF forms.
4-7.
Reduce the satisfiability problem for the formula
(x1 \/ -x2) & (-x1 \/ x2 \/ x3) to:
- 3-coloring
- clique
- subset problem
- interval computations
8-9. 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?
10. Describe a possible physical scheme that would enable us to solve
NP-hard problems in polynomial time. For extra credit: describe
two such schemes.