Exercises 34.1-5
Show that if an algorithm makes at most a constant number of calls to polynomial-time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial time. Also show that a polynomial number of calls to polynomial-time subroutines may result in an exponential-time algorithm.
Exercises 34.1-6
Show that the class P, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if L1, L2 ∈ P, then L1 ∪ L2 ∈ P, L1 ∩ L2 ∈ P, L1L2 ∈ P, L1c ∈ P, and L1* ∈ P.
Exercises 34.2-3
Show that if HAM-CYCLE ∈ P, then the problem of listing the vertices of a Hamiltonian cycle, in order, is polynomial-time solvable.
(Note 1: HAM-CYCLE is defined as "Does a graph G have a Hamiltonian cycle?")
(Note 2: "HAM-CYCLE ∈ P" means that HAM-CYCLE is polynomial-time solvable.)
Exercises 34.2-7
Show that the Hamiltonian-path problem can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem.
Exercises 34.4-7
Let 2-CNF-SAT be the set of satisfiable Boolean formula in CNF with exactly 2 literals per clause. Show that 2-CNF-SAT ∈ P. Make your algorithm as efficient as possible. (Hint: Observe that x ∨ y is equivalent to ¬x → y. Reduce 2-CNF-SAT to an efficiently solvable problem on a directed graph.)
Exercises 34.2-6
A Hamiltonian path in a graph is a simple path that visits every vertex exactly once.
Exercises 34.3-6
A language L is complete for a language class C with respect to polynomial-time reductions if L ∈ C and L' ≤P L for all L' ∈ C. Show that ∅ and {0, 1}* are the only languages in P that are not complete for P with respect to polynomial-time reductions.