2 Show that the hamiltonian path problem can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem.
3 Show that the <=p (polynomially reducible) relation is a transitive relation on languages. That is, show that if L1 <=p L2 and L2 <=p L3, then L1 <=p L3.
4 Prove that L <=p /L (complement of L) iff /L <=p L
5 Suppose someone gives you a polynomial time algorithm to decide formula satisfiability. Describe how to use this algorithm to find satisfying assignments in polynomial time.
6 Show that the subset-sum problem is solvable in polynomial time if the target value t is expressed in unary.
7 Why is the set of all programs countably infinite? (Hint : Think of the lengths of the programs. Another hint : Let k be the number of possible symbols in the alphabet. Think of base k numbers.)
8 Show that the set of all subsets of a countably infinite set
is uncountable.