Microsoft PowerPoint – lecture17 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 17, 3/20/18
Outline
• Probabilistic Turing Machines
• Probabilistic Complexity Classes RP, coRP
• Bipartite Matching and Determinants
• Multivariate Polynomial Zero Testing
Probabilistic Turing Machines
• A type of nondeterministicTM M, in which each step is
either a deterministic step (only one move) or a coin-flip
step: two possible moves, each with probability ½ .
• Probability(computation) = prob.(steps) = where k
is the number of coin-flip steps of the computation
• Prob(M accepts input x) = prob(accepting computations)
• Alternatively, we can view a PTM as a TM that starts by
generating a uniformly random bit string y of length k and
then computes deterministically on the given input x and
the random string y
• Can define different kinds of probabilistic complexity
classes depending on how acceptance is defined and what
kind of error is allowed.
2 k
Probabilistic Complexity Classes: RP
• RP (Randomized Polynomial time –Monte Carlo algorithms)
LRP iff there is a polynomial time PTM M such that
inputs x:
• xL Prob(M accepts x) ½
• xL Prob(M accepts x) =0 (no false positives)
• P RP NP
For NP, in the xL case, the requirement is that at least one
computation accepts, while for RP, at least ½ computations
must accept (condition is stronger); the condition in the xL
case is the same (no computation accepts)
Probabilistic Complexity Classes: coRP
• coRP = complements of languages in RP
LcoRP iff there is a poly-time PTM M such that
inputs x:
• xL Prob(M accepts x) =1 (no false negatives)
• xL Prob(M accepts x) ≤ ½
• P coRP coNP
Certificate version of RP, coRP
• L is in RP if there is a polynomial p, and a deterministic
polynomial time algorithm V(.,.) with two inputs such that
for all strings x
(| |) (| |)
(| |)
1
| { {0,1} | ( , ) accepts } | 2
2
{0,1} . ( , ) rejects
p x p x
p x
x L y V x y
x L y V x y
• L is in coRP if there is a polynomial p, and a deterministic
polynomial time algorithm V(.,.) with two inputs such that for
all strings x
(| |)
(| |) (| |)
{0,1} . ( , ) accepts
1
| { {0,1} | ( , ) rejects } | 2
2
p x
p x p x
x L y V x y
x L y V x y
Threshold ½ in definition arbitrary
• Could replace ½ with any other constant, eg. ¾ , 0.999.
• Classes stay the same.
Proof: Class RP: Given PTM M with threshold ½ , construct
PTM M’ that repeats the algorithm of M k times (with
independent random coin flips) and accepts if any of the k
repetitions accepts. Thus, M’ rejects if all k repetitions
reject.
• xL Prob(M accepts x) ½ Prob(M’ accepts)
• xL Prob(M accepts x) =0 Prob(M’ accepts x) =0
• We could even take k to be polynomial in the input size n,
and make the probability of error exponentially small
1 2 k
Relationship between the classes
P
NP coNP
RP coRP
Matching and determinants
• 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)
U V
• There is a combinatorial polynomial time algorithm for
determining whether a bipartite graph has a perfect
matching
Matching and determinants
• Alternative algebraic approach:
• Define nn matrix A whose rows correspond to the set
U={u1,…,un}, columns correspond to set V ={v1,…,vn},
and entries A[i,j]=variable xij if (ui,vj)ÎE, else 0
1
det ( ) [ , ( )]
n
i
A sign A i i
• The sum ranges over all permutations of {1,…,n}, and
sign is the sign of the permutation (+1 or -1)
• 1-1 correspondence between nonzero terms of the sum
and perfect matchings.
• detA is a polynomial in the variables xij, which is not
identically 0 iff there is a perfect matching.
Testing symbolic determinants
• If we are given a (square) matrix of integers (or rationals),
its determinant is an integer (or rational) of size (#bits in
the binary representation) polynomial in the size of the
input. We can compute the determinant in polynomial time,
eg. by Gaussian elimination
• Problem with matrix that contains variables: the
determinant is a polynomial that has in general
exponentially many terms – we cannot compute it explicitly
in polynomial time.
• But we only need to test if =0 polynomial.
• Key idea: Plug in random numbers for the variables and
test if the determinant of the resulting (constant) matrix is 0
Zeroes of polynomials
• A degree d polynomial p(x) in 1 variable has at most d
roots or it is identically =0.
• Proof: Induction on d.
– Basis d=0: p(x) =constant
– Induction step: If p(x) is nonzero and a is a root then
p(x)/(x-a) is a polynomial of degree d-1 has at most
d-1 roots, so p(x) has total at most d roots.
Zeroes of polynomials
• Schwartz-Zippel lemma: Let p(x1,…xm) be a nonzero
polynomial in m variables with total degree d. If we plug in
for the variables a tuple c of random values from a set of
size M then Pr[p(c)0] 1 – d/M .
• Proof: Induction on m.
Basis m=1: Follows from the 1-variable case
Induction step: Write p as a polynomial in x1 whose
coefficients are polynomials in the other variables:
Let i be the largest index such that pi is not the 0
polynomial (i exists because p is nonzero)
1 1 2
0
( , ) ( , )
d
i
m i m
i
p x x x p x x
Zeroes of polynomials
pi has total degree d-i
By the induction hypothesis, for a random tuple (c2,…,cm)
If a tuple (c2,…,cm) yields pi(c2,…cm)0, then p(x1,c2,…cm) is a
nonzero univariate polynomial of degree i at most i roots.
Hence:
2Pr[ ( , , ) 0] 1i m
d i
p c c
M
1 2Pr[ ( , , , ) 0] (1 )(1 ) 1m
d i i d
p c c c
M M M
Application to Bipartite Matching
• Number of variables m = #edges
• Total degree d=n
• Set M=2n and choose a random integer Î{0,1,…,2n-1} for
each variable and evaluate the resulting determinant
• If det¹0 then accept (there is a perfect matching)
• If det=0 then reject (probably there is no perfect matching)
• In Case 1, for sure there is a perfect matching
• If there is a perfect matching (i.e. the symbolic determinant
is nonzero) then the probability that Case 2 happens is 1/2
We can make the error probability arbitrarily small by
repeating the experiment several times (or taking larger M)
Another application to matching
• Exact Matching Problem
• Given bipartite graph with edges colored red or blue, and
a number k, does there exist a perfect matching with
exactly k red edges ?
• There are combinatorial deterministic polynomial time
algorithms for finding a perfect matching with the
maximum number of red edges, and for finding a perfect
matching with the minimum number of red edges.
• No deterministic P-time algorithm known for the exact
version. Open question if this is possible.
• Only probabilistic algorithm known, using a variation of
the determinant technique