Problem
1. Show that the reduction of the CNF-Satisfiability problem to the Clique Decision problem can be done in polynomial time.
2. Write a polynomial-time verification algorithm for the Hamiltonian Circuits Decision problem.
3. Show that the reduction of the Hamiltonian Circuits Decision problem to the Traveling Salesperson (Undirected) Decision problem can be done in polynomial time.
4. Show that the reduction of the Traveling Salesperson (Undirected) Decision problem to the Traveling Salesperson Decision problem can be done in polynomial time.