===========================================================================
CSC 363                     Homework Exercise 6                 Winter 2008
===========================================================================

Due: by 6pm on Wed 26 Mar
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure
that you use notation and terminology correctly, and that you explain and
justify what you are doing.  Marks *will* be deducted for incorrect or
ambiguous use of notation and terminology, and for making incorrect,
unjustified, ambiguous, or vague claims in your solutions.

In your reductions, you may only make use of languages shown to be
NP-complete during lectures, unless specified otherwise.


1.  Show that the following language is NP-hard.
        A_NTM = { <M,w> : M is a NTM that accepts input w }
    Can you also show that A_NTM is NP-complete?  Justify.


2.  Write a detailed proof that 5-SAT is NP-complete, where
      5-SAT = { <F> : F is a satisfiable propositional formula in 5-CNF }
    (a formula is in 5-CNF if it is in CNF and each clause contains exactly
    5 literals).  Your answer will be marked on its structure as much as on
    its content.

    Hints:  Remember that literals can be repeated inside clauses, e.g.,
    (z \/ z \/ ~y \/ x \/ ~w) is an acceptable clause.
    There is a very short reduction for this language.


3.  Write a detailed proof that HAM-CYCLE is NP-complete, where
      HAM-CYCLE = { <G> : G is an undirected graph that contains a simple
                          cycle that includes every vertex exactly once }.
    Your answer will be marked on its structure as much as on its content.

    Hints:  You may make use of the fact that the following language is
    NP-complete:
      st-HP = { <G,s,t> : G is an undirected graph that contains a
                          Hamiltonian path from s to t }.
    Be careful: the reduction is easy, but not trivial.