Microsoft PowerPoint – lecture25 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 25, 4/17/18
Outline
Counting Problems
• Class #P
• Reductions
• #3SAT is #P-complete
• # Bipartite Perfect matchings
• # Cycle Covers in directed graphs
• Permanent
• Other problems
Counting Problems
• #SAT: Given a Boolean formula, how many satisfying
assignments does it have?
• #3-Colorings: Given a graph, how many 3-colorings does
it have?
• #Hamiltonian Circuits: Given a graph, how many
Hamiltonian circuits does it have?
• #Perfect Matchings: Given a graph, how many perfect
matchings does it have?
• #Spanning Trees: Given a graph, how many spanning
trees does it have?
• #Maximal Cliques: Given a graph, how many maximal
cliques (i.e. not subsets of other cliques) does it have?
Counting Problems
• Graph s-t Edge Reliability: Given a (directed or
undirected) graph G, suppose each edge fails
independently with probability ½.
• What is the probability that there is a path from s to t?
• Discrete probabilities involve counting: How many
subgraphs of G have a path from s to t?
• Probability of s-t connectivity = ratio of this count to #2 edges
Easy vs. Hard Counting Problems
• #SAT, #3-Colorings, #Hamiltonian-paths are obviously at
least as hard as NP: The existence question ( satisfying
assignment?, etc.), equivalent to “is count≥1?” is NP-hard.
• For #Spanning Trees, #Perfect Matchings, s-t Edge
Reliability, the existence question can be solved in
polynomial time, and for #Maximal Cliques existence is
trivial (every graph has a maximal clique).
• Some counting problems are easy and some hard:
• #Spanning Trees can be computed in polynomial time
(Kirchoff’s matrix tree theorem)
• #Perfect Matchings, s-t Edge Reliability, #Maximal Cliques
are just as hard as #SAT.
Class #P (“Sharp P” or “Number P”)
• Class of functions, not decision problems
• A function f is in #P if there is a poly-time NTM M such that
for every input x, f(x)= #accepting computations of M
• Equivalently, f is in #P if there is a poly-balanced and poly-
decidable binary relation R(.,.) such that for every x,
f(x) = |{ y | R(x,y) }|.
• That is, f(x) is the number of certificates (solutions) that
certify that the input x is in the NP language
LR = { x | y.R(x,y) }
Note: The same language may have different R (and different NTM M)
which may lead to different counting problems
• All the previous examples of counting problems are in #P
#P vs. other classes
• : Problems we can solve in Ptime with #P oracles
•
Given x, we can enumerate in PSPACE every possible
certificate y of length up to p(|x|), check if it satisfies R(x,y)
and keep a count.
• Obvious that NP
• Toda’s Theorem:
#PP
#P#P, P PSPACE
#PP
#PPH P
P
NP coNP
PH
P#P
PSPACE
Reductions and #P-completeness
• Karp- ( many-to-one) reduction from counting problem A to B
BA B if A P
• Parsimonious reduction from A to B: Special case where g =
identity, i.e. reduction f preserves # solutions
• Not always possible to do parsimonious reduction: If #SAT
has parsimonious reduction to #Perfect Matchings then P=NP
• It is often convenient to use Cook reductions:
instance x of A instance f(x) of Bf
# solutions of f(x)# solutions of x
g
where f, g are polynomial time computable
• B is #P-complete: B is in #P and every A in #P reduces to B
#3SAT is #P-complete under
parsimonious reductions
• Cook’s reduction to 3SAT is parsimonious
• Problem in #P for relation R: Given input x, compute
count(x) = |{ y | R(x,y) }|.
• Construct poly-size circuit C for R: C has inputs x,y and for
every x,y assignment, C(x,y)=1 iff R(x,y) holds.
• Fix the values of the circuit inputs for x
circuit C’ with inputs y such that C’(y)=1 iff R(x,y) holds
| {y | C’(y)=1} | = | { y | R(x,y) } | = count(x)
• Introduce variables z for the gates and construct 3CNF
formula (y,z) such that an assignment to y,z satisfies iff
z are the values of the gates for input y and C’(y)=1.
| { (y,z) | (y,z) =1} | = | { y | C’(y)=1} | = count(x)
Counting for other NP-complete problems
• Many other NP-completeness reductions are parsimonious
or can be made parsimonious (sometimes with effort)
• Same applies to their complements, though technically the
reduction is not parsimonious:
If we know how many strings y of length p(n) satisfy R(x,y)
then we can deduce how many do not satisfy it
• Example: Satisfiability for DNF formulas is in P.
• But #3DNF-SAT is #P-complete:
• If is a 3CNF formula with n variables, then its negation
is equivalent to a 3DNF formula .
#satisfying assign. of = 2ⁿ – #satisfying assign. of
Perfect Matchings in Bipartite Graphs
Cycle Covers in Directed Graphs
• Bipartite graph: Nodes partitioned into two sets: UV, all
edges across the partition: EUV
• Matching: set of disjoint edges
• Perfect matching: includes all the nodes (possible only if
|U|=|V|=n)
• Cycle Cover in Directed graph: set of node-disjoint
cycles that covers (includes) all nodes.
• Correspondence between perfect matchings in bipartite
graphs and cycle covers in directed graphs
Example
1v
2v
3v
1u
4v
2u
4u
3u
1 2
34
( , )i ju vEdge in bipartite graph corresponds to
edge ij in directed graph
Matrix of directed (or of bipartite) graph
Adjacency matrix A of directed graph D:
nn matrix A where A[i,j]=1 if edge ij else 0 .
For a bipartite graph G with node sets U={u1,…,un}, V ={v1,…,vn}
Matrix A whose rows correspond to U, columns to V,
and A[i,j]=1 if (ui,vj)ÎE, else 0
Perfect matchings of G cycle covers of D
sets of n nonzero entries of the matrix no two of which are in the
same row or column permutations of {1,…,n}
(row 1, col (1)), (row 2, col (2)), …, (row n, col (n)),
Example
1v
2v
3v
1u
4v
2u
4u
3u
1 2
3
4
1 0 1 0
1 0 1 0
0 1 0 1
0 1 1 1
Permanent of a matrix
1
det ( ) [ , ( )]
n
i
A sign A i i
where sum ranges over all permutations of {1,…,n}
1
per( ) [ , ( )]
n
i
A A i i
Like the determinant:
except without the sign() factor; all the terms are added
• Determinants of integer matrices can be computed in
polynomial time, eg. by Gaussian elimination
• Permanent appears to be much more difficult
Permanent of a 0-1 matrix
where sum ranges over all permutations of {1,…,n}
1
per( ) [ , ( )]
n
i
A A i i
• If A = matrix of a directed graph D (or of bipartite graph G),
then per(A) = #cycle covers of D = #perfect matchings of G
• nonzero terms in permanent cycle covers of D
perfect matchings of G
Theorem: All three problems are #P-complete:
Computing the permanent of a 0-1 matrix
Counting the # perfect matchings of a bipartite graph
Counting the #cycle covers of a directed graph
Reduction from #3SAT
• Not a parsimonious reduction (otherwise it would imply
P=NP)
• Reduction for directed #cycle covers
• Allow first graphs with integer weights on edges
permanent of general integer matrix,
and then we will eliminate weights
• Weight of cycle cover: multiply the weights on the edges
• Total weight = add the weights of all the cycle covers =
per(A)
Reduction
• Variable gadgets, clause gadgets, interconnections
variable gadget
x truex false
clause gadget
a false
b false
c false
abc
a,b,c false no cycle cover
Every other assignment to a,b,c
exactly 1 way to cover clause
gadget
Interconnection
• Purple “edges” are not actual edges:
• Interconnection between purple edge “a false” in a
clause gadget with the edge “a true” in variable gadget to
enforce consistency: one or the other traversed.
• Would like interconnection to be “exclusive-or” (XOR)
saying that exactly one of the two is traversed. Cannot
do exactly because otherwise we would have a
parsimonious reduction.
• Use weights to get desired effect.
Interconnection XOR gadget
1
2’ 2
1’
a
c
d
b
-1
2
3-1
-1
1
1’
2’ 2
Other edges have weight 1
Property of XOR gadget:
All Cycle covers cancel out (net contribution =0) except for those that
contain exactly one of the pairs (1a, c1’) or (2c, a2’) that
contribute 4 each
Traversing purple “edge” 11’ corresponds to edges 1a, c1’
Traversing purple “edge” 22’ corresponds to edges 2c, a2’
+
Schematic depiction
Overall Graph for 3SAT formula
1x 2x 3
x rx
2C kC
0 00 01 1 1 1
+ +
+
3211 xxxC
Analysis
• # XOR gadgets = # literal occurrences = 3k
• Every satisfying assignment corresponds to a cycle cover
that contributes (weights 4 for each XOR gadget are
multiplied)
• Total weight of all cycle covers =
where s = # satisfying assignments.
• Thus, if A is the matrix of this weighted directed graph,
then from per(A) we can infer the # satisfying assignments:
34 k
34 ks
3per(A) 4 ks
Elimination of weights
• Small positive weights 2, 3: replace with small gadgets
2 3
• Weight -1. Do calculations mod N = 2ⁿ+1, where n is
suitably large, say n>r+6k, so that N > per(A)=
• -1 mod N is then = N-1 = 2ⁿ.
• Replace -1 edges with following gadget:
34 ks
-1
u u
u u u u
v v
v v v v
n
Analysis ctd.
• If D’ is the resulting directed graph and A’ its adjacency
matrix, then per(A’) = #cycle covers of D’ =
per(A) mod N = where s =#satisfying
assignments of the given formula
• So, if we could compute permanent of 0-1 matrices in
polynomial time, we would compute per(A’), then
compute its remainder mod N, and divide by to
obtain s.
34 ks
34 k
Other #P-complete Problems
• #Matchings in Bipartite Graph: Count total number of all
matchings of any size.
• #2SAT: Given a 2CNF formula, we can determine in
polynomial time whether it is satisfiable, but counting
#satisfying assignments is #P-complete.
• Monotone #2SAT: Given 2CNF formula with no negation.
Counting is still #P-complete
• Minimal Node Covers: Count node covers that do not
contain properly any other node cover
• #Prime Implicants of a Monotone 2CNF formula
(prime implicant= minimal partial truth assignment that
implies formula true)
• #Directed trees: Given directed graph, count #rooted
subtrees (not necessarily spanning).
#P1: Unary #P
• Many combinatorial counting questions ask, how many
objects are there of a certain type for a given size n.
For example
• How many binary trees with n nodes?
• How many planar graphs with n nodes?
…
• Some of them we can answer, some seem very hard.
• In this case the input is just n – given in unary.
• Class #P1 : Analog of #P for unary input (i.e. input =1ⁿ)
• There is a complete problem, but it is open to show
completeness for one of the well-studied specific graph
counting problems