hmwk6.dvi
COMS 4236 Homework 6
Mengqi Zong < mz2326@columbia.edu >
April 19, 2018
Problem 1
For any input x, let the Boolean expression in disjunctive normal form in the input
be d. We first guess a Boolean expression c in conjunctive normal form that has at
most B clauses. Let a be an assignment to the Boolean expression. Then (d − c)(a)
denote that the value of expression d − c for assignment a. We now could show that
the language L defined by this problem is
L = {x : ∃ c ∀a such that (d− c)(a) = 0}
Since B is given in unary and c has at most B clauses, we can verify if (d− c)(a) = 0
for any a in poly(x) time. Then by the definition of the certificate version of Σ2, we
know that L ∈ Σ2. So this problem is in Σ2.
Problem 2
1. It’s easy to show that DFA Intersection problem is in NPSPACE. We simply guess a
string by first guessing its length and then guessing every tape cell of the string. Then
verify if this string can be accepted by all n DFAs. Trivially, we can use n work tapes
and each tape that initially stores the string x. So, this problem is in NPSAPCE. By
Savitch’s Theorem, this problem is in PSPACE.
2. We will show that the DFA Intersection problem is PSPACE-hard by reducing LBA
problem to this problem.
1
Given an input x to the LBA, we will construct the DFAs as follows:
Let n = |x|+ 2 (including endmarkers), we construct n DFAs, A1, …, An. Suppose the
LBA has a transition (q, a, i) → (p, b, j). Then for all DFA except Ai, Aj , they will
have a transition (a, i) → (b, j). As to Ai, it will have a transition (p, a, i) → (b, j).
As to Aj, it will have a transition (a, i) → (q, b, j). And when LBA accepts, mark all
DFAs corresponding states accepting.
As we can see, all DFAs are different, and LBA accepts x if and only if all DFAs accepts
x. So, the DFA intersection problem is PSPACE-hard.
To sum up, the DFA intersection problem is PSPACE-hard.
Problem 3
1. It is trivial that #2SAT is in #P. Now we will prove that #2SAT is #P-hard by
reducing #Matchings to #2SAT.
For any #Matchings problem, given an undirected graph G, we construct a 2SAT
monotone formula as follows:
• For each edge (i,j) in G, we construct a Boolean variable.
• For each pair of edges that share the same node, we create a new term in the
2SAT.
For example, suppose there are three edges that connect to node 1: (1,2), (1,3),
(1,4). And we use Boolean variables v2, v3, v4 to represent each edge. Since there
are
(
3
2
)
= 3 pairs of edges, we create 3 new terms: (v2 ∨ v3), (v2 ∨ v4), (v3 ∨ v4).
• Combine all terms together with ∧, we get the #2SAT monotone formula φ.
Now we will show that the number of satisfying assignments of φ equals to the number
of matchings in G. For every satisfying assignment of φ, for each variable vi, if vi = 1,
then the edge represented by vi is not in the matching. That is, all the edges whose
vi = 0 form a matching of G. We will show that all those edges don’t share the same
node. If there is one pair of edges share the same node, since all edges in the matching
is equivalent to a variable vi = 0, then one term in the #2SAT will not be satisfied,
2
then the formula φ will not be satisfied. This contradicts with the fact that the as-
signment is a satisfying assignment of φ. So, #2SAT is #P-hard.
To sum up, #2SAT is #P-complete.
2. It is trivial that #Node Covers is in #P. We will prove that #Node Covers is #P-
hard by reducing #2SAT to #Node Covers.
For any #2SAT problem, given a 2SAT formulas φ, we will create a undirected graph
G as follows:
• For every variable vi in φ, we create a node ni in G.
• For every term (vi ∨ vj), we create an edge (ni, nj) in G.
Now we will show that the number of node covers of G equals to the number of satisfy-
ing assignment of φ. For every set of nodes that cover all edges in G, since each edge in
G represents a term in the #2SAT formula φ, then covering all nodes means all terms
in φ are satisfied. So, each node cover of G is equivalent to a satisfying assignment to
φ. And each nodes in the node cover means the variable represented by this node is 1.
So, #Node Covers is #P-hard.
To sum up, #Node Cover is #P-complete.
3