课程名称︰资讯工程理论基础
课程性质︰选修
课程教师：吕育道
开课学院：电资学院
开课系所︰资工所
考试日期（年月日）︰2016.11.29
考试时限（分钟）：
试题 :
Theory of Computation
Midterm Examination on November 29, 2016
Fall Semester, 2016
Problem 1 (25 points)
Show that for n > 3, n-sat is NP-complete. (You don't need to show that n-sat
is in NP.)
Ans: We reduce 3-sat to n-sat as follows. Let ψ be an instance of 3-sat. For
any clause (a Ｖ b Ｖ c) of ψ, replace it with (a Ｖ b Ｖ c Ｖ … Ｖ c).
╰──n-2 ─╯
By repeating this procedure for all clauses of ψ, we derive a new
boolean expression ψ' for n-sat. Then ψ is satisfiable if and only if
ψ' is satisfiable.
Problem 2 (25 points)
Let G = (V, E) be a graph and K be a positive integer. LONGEST PATH ask
if there is a simple path which contains at least K edges in G. Show that
LONGEST PATH is NP-complete. (You need to show that LONGEST PATH is in NP.)
Ans: First we show that Longest Path is in NP. Given an instance G, we guess
a set of edges of size at least K and at most |G| and examine if it is a
simple path in G. This can be done in polynomial time. We now proceed to
show that LONGEST PATH is NP-hard by reducing HAMILTONIAN PATH to
LONGEST PATH. Given an instance G of HAMILTONIAN PATH, we create an
instance (G', K) of LONGEST PATH as follows: Take G' = G and set
K = |V| - 1. Then there exists a simple path of length K in G' if and
only if G contains a Hamiltonian path.
Problem 3 (25 points)
Prove that the language Ψ is NP-complete, where Ψ = {(N, x, 1^t)│a
nondeterministic Turing Machine N that accepts x within time t}. Recall that
1^k denotes the string consisting of k 1s. Do not forget to show Ψ is in NP.
Ans: We first show that Ψ is in NP. With the input (N, x, 1^t), we simulate
N nondeterministically on x up to t steps and accept if N accepts x. The
algorithm obviously runs in polynomial time. Furthermore, (N, x, 1^t)
is in Ψ if and only if there is a path such that N(x) = "yes" within
t steps. We next show that Ψ is NP-hard. Let L ∈ NP be accepted by a
nondeterministic Turing Machine N that runs in polynomial time n^c for
some constant c. To reduce L to Ψ, simply map the input x to the
triple (N, x, 1^(n^c)). The reduction can evidently be performed in
polynomial time. It is clear that x ∈ L iff (N, x, 1^(n^c)) ∈ Ψ.
Problem 4 (25 points)
DNF NON-TAUTOLOGY asks if a DNF is not a tautology. Prove that this problem
is NP-complete. (You need to show that DNF NON-TAUTOLOGY in NP.)
Ans: The problem is equivalent to asking if there exists a truth assignment
that makes the DNF false. This problem is in NP because one can
nondeterministically guess a truth assignment and accept the input
DNF formula if it is not satisfied by the truth assignment. We shall
reduce the NP-complete SAT to it. The reduction applies de Morgan's laws
to convert the input CNF formula ψ into a DNF φ of about the same
length. Then ψ is satisfiable if and only if φ is not a tautology.