4. In HAMPATH, how can the checking for a Hamiltonian path be done in
O(n 4 ) time?
5. Show that a k-clique must have exactly k(k − 1)/2 edges.
6. Find a 4-clique in the graph below. Prove that the graph has no 5-clique.
7. Give the details of the argument in Example 14.8.
8. Show that P is closed under union, intersection, and complementation.
14.6 Polynomial-Time Reduction
One way to unify different cases is to see if we can reduce them to each other, in
the sense that if one is tractable, the others will be tractable also.
Definition 14.3
A language L 1 is said to be polynomial-time reducible to another language L 2 if
there exists a deterministic Turing machine by which any w 1 in the alphabet of
L 1 can be transformed in polynomial time to a w 2 in the alphabet of L 2 in such a
way that w 1 ∈ L 1 if and only if w 2 ∈ L 2 .
Example 14.9
In the satisfiability problem we put no restriction on the length of a clause. A
restricted type of satisfiability is the three-satisfiability problem (3SAT) in which
each clause can have at most three literals. The SAT problem is polynomial-time