Microsoft PowerPoint – lecture18 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 18, 3/22/18
Outline
• Randomized Primality Test
• More Probabilistic Complexity Classes
ZPP, BPP, PP
• Relationships
Randomized Test for Primality:
Primes coRP
• Based on two properties of primes:
1. Fermat’s Theorem: If p is prime then for all aÎZp+ ={1,..,p-1}
• Given a number p, if for some aÎZp+,
then p must be composite
– For example, for p=6, take a=2:
• Most composites fail this test badly: for at least ½ the a’s.
• But few composites don’t (Carmichael numbers pass the
test for all a relatively prime to p, e.g. 561=3·11·17).
• What to do about them?
1 1modpa p
1 1modpa p
52 32 2 mod6
Properties ctd
2. Square root of 1: If p is prime then 1 has only two square
roots mod p: 1 and -1 (i.e. p-1)
• Every composite number fails property 1 or 2: There is an
aÎZp+ such that or a²=1 mod p, but a≠1,-1
Example: p=15.
For a=4, 42=16=1 mod15 and 4 ≠1,-1 mod15
15 is composite
1 1modpa p
Proofs of properties
1. Proof of Fermat’s theorem:
For every aÎZp+, and 0
• We can also make the probability of error
exponentially small:
Repeat the algorithm k = poly(n) times and
output the majority decision: accept if more than
half of the repetitions accept, otherwise reject
• Then probability of error becomes ( ) poly( )2 2k n
Proof of error reduction for BPP
• Chernoff bound: Let z1 , …, zk be independent random
variables that take value 1 (resp. 0) with probability p
(resp. 1-p), and let their sum be Z=zi. Then, for all 0≤≤1
2
2Pr [ (1 ) ]
pk
ob Z pk e
• Let zi=1 if i-th repetition gives the correct answer, else 0
• xL Prob(M accepts) =p ¾ .
After k repetitions with =1/3: (1-pk k/2
Prob[ M’ rejects] = P[Z ≤ k/2] 24
k
e
• xL Prob[M’ accepts] (similarly)24
k
e
Class PP
LPP iff there is a polynomial time PTM M such that
inputs x:
• xL Prob(M accepts x) > ½
• xL Prob(M rejects x) ≥ ½
• Difference with BPP is that in BPP the probability is
bounded away from ½ , here it is not.
• Not very useful for probabilistic algorithms: cannot tell the
difference reliably between the two cases
• Typical problem: Given Boolean formula, are more than ½
of the truth assignments satisfying?
Comparison of classes
Probability of acceptance
Class xÎL xL
P 1 0
NP >0 0
coNP 1 <1
RP ≥ ½ 0
coRP 1 ≤ ½
BPP ≥ ¾ ≤ ¼
PP > ½ ≤ ½
Relationship between the classes
P
NP coNP
NPcoNP
RP coRPZPP
BPP
PP
Completeness
• RP, coRP, ZPP, BPP are all “semantic classes”
• For example, given a PTM M it is undecidable to
determine whether M accepts every input with
probability either ¾ or ≤ ¼ (but not in-between).
• No complete problems known for these classes
• PP is a syntactic class: Can associate with every
PTM M the language of input strings that M accepts
with probability > ½ .
• PP has complete problems. For example,
{Boolean formula | satisfied by > ½ truth assignments}
(HW exercise)