• Site Map

• Lectures

• Homework

• Tests/Exam

• Main Webpage

Homework Exercise 6

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.