Chapter 10 --- Little Quiz                                                        

For each problem, select an incorrect item.

1. (a) Intractable problems can only be solved in exponential time.(b) Problems requiring polynomial time are solvable in amounts of time which we can tolerate.(c) Problems requiring exponential time generally cannot be solved in reasonable time except for small instances.(d) Reduction of tractable or intractable problems may be done in exponential time.

2.(a) The class P of problems solvable by DTMs in polynomial time seems not equal to the class NP of problems are solvable by NTMs in polynomial time.(b) Either all problems in NP have polynomial-time deterministic solutions or none do.(c) Whether the class P is equal to the class NP is an open problem.(d) NP means problems solvable by an NTM in polynomial time, and so they can be solved by a computer program in language C in polynomial time.

3. (a) The minimum-weight spanning tree problem is solvable in polynomial time.(b) The traveling salesman problem seems only solvable in exponential time.(c) The satisfiability problem is solvable in polynomial time.(d) The Hamilton circuit problem seems only solvable in exponential time.

4. (a) To prove a problem P₂ not in P, we can reduce a problem P₁ also not in P to it.(b) L is NP-complete if L is in NP, and for every language L' in NP, there is a polynomial-time reduction of L' to L.(c) If some NP-complete problem P is in P, then P ¹ NP.(d) If P₁ is NP-complete, P₂ is in NP, and there is a polynomial-time reduction of P₁ to P₂, then P₂ is NP-complete.

5. (a) SAT problems are NP-complete.(b) CSAT problems are NP-complete.(c) 3SAT problems are NP-complete.(d) 2SAT problems are NP-complete.