CIS 480 - Computer Theory - Spring 2000
HOMEWORK #8
DUE: Wednesday, May 3rd, Beginning of Class

NOTE: This will only be accepted for late credit (up to 80%) through 5 pm 
on Friday, May 5th, so that its solution can be posted to the course web 
page sometime after 5 pm on Friday, May 5th.

1.   Consider the LONGEST CYCLE problem (Lewis and Papadimitriou, p. 332):
        "Given a graph, and an integer K, is there a cycle, with NO 
	repeated nodes, of length at least K?"

        Prove that the LONGEST CYCLE problem is NP-complete.

        (Hint 1: What happens to this problem if K is restricted to be 
	equal to the number of nodes in the 
        graph?)
        (Hint 2: Try reducing the Hamiltonian Circuit problem to this)

2.   Consider the problem ETtm, the problem of deciding if a TM halts on 
the empty tape
        (a)   Is ETtm definitely in P, definitely in NP, or definitely in 
	neither? 

        (b)   Explain your answer to (a).

3.   Consider the Hamiltonian Circuit problem, which is known to be 
NP-Complete.
        (a)   Since you know that this problem is NP-Complete, what does 
	this infer, if anything, about 
        whether or not an algorithm exists for this problem?

        (b)  is Hamiltonian Circuit undecidable or decidable? Explain 
	your answer.

4.   Assume that someone ever manages to find/design a polynomial-time 
algorithm for the Hamiltonian Circuit problem. 
        (a) This would have certain important implications for the set of 
	NP-Complete problems. What would 
        it mean?

        (b) This would also have certain important implications for P and 
	NP. What would it mean?

5.    Assume that each of the following functions gives the time (number 
of steps) needed by particular deterministic Turing Machines to decide an 
input of length n: (^ is used, below, as the exponentiation operator)
        (1) 48n^3 + 653n + 10,438

        (2) 2^n + 0.5n + 7

        (3) 589

        (a) Give the time complexity for each of these TM's, using big-O 
	notation.

        (b) Which of these TM's represent polynomial-time solutions? 
	(List all that apply)

        (c) Which of these TM's represent exponential-time solutions? 
	(List all that apply)