课程名称︰资讯工程理论基础
课程性质︰必修
课程教师︰吕育道
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰2013.12.17
考试时限（分钟）：180
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
Theory of Computation
Mid-Term Examination on December 17, 2013
Fall Semester, 2013
Problem 1 (25 points).
Show that NP = coNP if there exists an NP-complete language that belongs in
co-NP.
Proof.
Suppose X is NP-complete and X ∈ coNP. Let a polynomial-time NTM M decide X.
For any language Y ∈ NP, there is a reduction R from Y to X because X is
NP-complete. Now, X ∈ coNP implies Y ∈ coNP by the closure of reduction;
hence
NP ⊆ coNP.
_
On the other hand, suppose Y ∈ coNP. Then there is a reduction R' from Y to X
_
because Y ∈ NP and X is NP-complete. As a result, for all input strings x,
_
x ∈ Y iff R'(x) ∈ X.
_
This implies Y ∈ coNP by the closure of reduction and the assumption of
X ∈ coNP. Consequently, Y ∈ NP and
coNP ⊆ NP.
Thus, NP = coNP.
Problem 2 (25 points).
A cut in an undirected graph G = (V, E) is a partition of the nodes into two
nonempty sets S and V-S. MAX BISECTION asks if there is a cut of size at least
K such that |S| = |V-S|. It is known that MAX BISECTION is NP-complete.
BISECTION WIDTH asks if there is a bisection of size at most K such that
|S| = |V-S|. Show that BISECTION WIDTH is NP-complete. You do not need to show
it is in NP.
Proof. See pp. 368 369 in the slides.
Problem 3 (25 points).
Show that 6-COLORING is NP-hard. (6-COLORING asks if a graph can be colored
by 6 or fewer colors such that no adjacent nodes have the same color). You do
not need to show it is in NP. Recall that 3-COLORING is NP-complete.
Proof.
We reduce 3-COLORING to 6-COLORING. Given a graph G(V, E) for 3-COLORING, the
reduction outputs a graph G'(V', E') by adding 3 new nodes with edges between
each of the 3 nodes and all the other nodes in V. That is,
V' = V ∪ {x_1, x_2, x_3} and
E' = E ∪ {{x_i, v} | v ∈ V', i = 1,2,3, x_i ≠ v}.
If G ∈ 3-COLORING, then G' ∈ 6-COLORING because 3 or fewer colors for the
nodes in V and an additional 3 colors for those in {x_1, x_2, x_3} suffice to
make a legal coloring. Conversely, consider a legal coloring of G' with 6 or
fewer colors. In such a coloring, {x_1, x_2, x_3} use up 3 colors, leaving at
most 3 colors for the nodes in V.
Problem 4 (25 points).
We know that 3-SAT is NP-complete. Show that for n > 3, n-SAT is also
NP-complete. (You don't need to show that is in NP.)
Proof.
We reduce 3-SAT to n-SAT as follows. Let ψ be an instance of 3-SAT. For any
clause (a∪b∪c), we replace it with (a∪b∪c∪…∪c). By repeating this
╰─┬─╯
n-2 times.
process in all the clauses of ψ, we get a new boolean expression ψ' ∈ n-SAT.
Now, we proceed to show that this is a reduction from 3-SAT to n-SAT as
follows:
(=>) From the construction, we see that if a truth assignment satisfies ψ,
then it must satisfy ψ'.
(<=) Let's notice that if a truth assignment satisfy ψ', then it must also
satisfy ψ.
From this, we then deduct that is satisfiable if and only if ψ' is
satisfiable as well, hence 3-SAT is reducible to n-SAT, probing that n-SAT is
NP-complete.