CS 5315, Test 2, Spring 2007
Name
(Please do not forget to put your name on all extra sheets of
paper)
1. A "cube-checker" is, by definition, a program which checks
whether a given program p always correctly computes the cube
n^3 for a given input n. Prove that cube-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*x2 into DNF and CNF forms.
4-7. Reduce the satisfiability problem for the formula (x1 \/ -x2 \/
-x3) & (-x1 \/ x2 \/ x3) to:
- 3-coloring
- clique
-
subset problem
- interval computations
8-9. 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?
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.
11. What is Kolmogorov complexity? Estimate the Kolmogorov
complexity of a string 001001...001001 (2,007 times). For extra
credit: prove that Kolmogorov complexity is not computable.