{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;
\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;
\red192\green192\blue192;}{\stylesheet{\widctlpar\adjustright \fs20\cgrid \snext0 Normal;}{\s1\qc\keepn\widctlpar\adjustright \b\fs20\cgrid \sbasedon0 \snext0 heading 1;}{\*\cs10 \additive Default Paragraph Font;}{\s15\widctlpar
\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid \sbasedon0 \snext15 header;}{\s16\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid \sbasedon0 \snext16 footer;}{\*\cs17 \additive \sbasedon10 page number;}}{\info{\title HUMBOLDT STATE UNIVERSITY}
{\author Dr. Hal Campbell}{\operator Tuttle}{\creatim\yr2000\mo4\dy26\hr13\min10}{\revtim\yr2000\mo4\dy26\hr13\min10}{\printim\yr1999\mo3\dy10\hr11\min37}{\version2}{\edmins0}{\nofpages1}{\nofwords281}{\nofchars1603}{\*\company CNRS - HSU}
{\nofcharsws1968}{\vern113}}\widowctrl\ftnbj\aenddoc\lytprtmet\formshade\viewkind1\viewscale100\pgbrdrhead\pgbrdrfoot \fet0\sectd \linex0\endnhere\sectdefaultcl {\header \pard\plain \s15\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid {\fs18 
CIS 480 - Homework #8\tab \tab p. }{\field{\*\fldinst {\cs17\fs18  PAGE }}{\fldrslt {\cs17\fs18\lang1024 1}}}{\fs18 
\par Sharon Tuttle - Spring 2000
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \s1\qc\keepn\widctlpar\outlinelevel0\adjustright \b\fs20\cgrid {CIS 480 - Computer Theory - Spring 2000
\par }\pard\plain \qc\widctlpar\adjustright \fs20\cgrid {\b HOMEWORK #8
\par DUE: Wednesday, May 3rd, Beginning of Class}{\b\fs24 
\par }\pard \widctlpar\adjustright {\b 
\par 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.
\par 
\par }{1.   Consider the }{\b LONGEST CYCLE}{ problem (Lewis and Papadimitriou, p. 332):
\par         "Given a graph, and an integer K, is there a cycle, with NO repeated nodes, of length at least K?"
\par 
\par         Prove that the }{\b LONGEST CYCLE }{problem is NP-complete.
\par 
\par         (Hint 1: What happens to this problem if K is restricted to be equal to the number of nodes in the 
\par         graph?)
\par         (Hint 2: Try reducing the }{\b Hamiltonian Circuit}{ problem to this\'85)
\par }{\b 
\par }{2.   Consider the problem }{\b ET}{\sub TM}{, the problem of deciding if a TM halts on the empty tape
\par         (a)   Is }{\b ET}{\sub TM}{ definitely in }{\b P}{, definitely in }{\b NP}{, or definitely in neither? 
\par }{\b 
\par }{        (b)   Explain your answer to (a).
\par }{\b 
\par }{3.   Consider the }{\b Hamiltonian Circuit}{ problem, which is }{\b known}{ to be }{\b NP-Complete}{.
\par }{\b         }{(a)   Since you know that this problem is NP-Complete, what does this infer, if anything, about 
\par         whether or not an algorithm }{\b exists}{ for this problem?
\par 
\par         (b)  is }{\b Hamiltonian Circuit}{ undecidable or decidable? Explain your answer.}{\b 
\par 
\par }{4.   Assume that someone ever manages to find/design a polynomial-time algorithm for the }{\b Hamiltonian Circuit }{problem. 
\par         (a) This would have certain important implications for the set of NP-Complete problems. What would 
\par         it mean?
\par 
\par         (b) This would also have certain important implications for P and NP. What would it mean?
\par 
\par 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 }{\b n}{:
\par         (1) 48n}{\super 3}{ + 653n + 10,438
\par 
\par         (2) 2}{\super n}{ + 0.5n + 7
\par 
\par         (3) 589
\par 
\par         (a) Give the }{\b time complexity}{ for each of these TM's, using big-O notation.
\par 
\par         (b) Which of these TM's represent }{\b polynomial}{-time solutions? (List all that apply)
\par 
\par         (c) Which of these TM's represent }{\b exponential}{-time solutions? (List all that apply)
\par 
\par }}