Chapter 7 : Relations Between Complexity Classes
Complexity class parameters :
1. Model: multi string Turing machine
2. Mode : deteriminstic v.s nondeterministic
3. Resource wish to bound : time v.s space
4. specify of bound : f(N)->N
Proper complexity function :
1. n f(n+1)≧f(n)
2. n |x| = n (s,>,x,>,'',>,'',...,>,'')
t
├ (h, x, >, _j2,>, ...>,_jk-1,>~f(n)
M
where t = O(n+f(n)) and ji = O(f(n))
ie: Mf halt after O(n+f(n)) steps and used O(f(n)) space.
Remark :
Condition 2 is used to prevent some tricky function such
that is very complex and engouh to encode some self
description function (reference Gap theorem) .
Proposition :
if f, g are both proper then f+g, f*g, 2^g are also proper.
Proposition :
if TM M decide L within time (or space) f(n) and f(n) is proper,
then there is a M' decide L in exactly f(n) time (or space)
Definition of coC :
Let L in Σ*, L' = Σ*\L
C = {L:L in C},
coC = {L' : L in C}
Proposition :
For any deterministic class C, coC = C.
The hierarchy theorem :
Hf : Time bound version of halting problem.
Hf = {<M,x> : M accepts input x after at most f(|x|) steps }
Lemma : Hf in TIME(f(n)^3)
Proof :
Because f(n) is proper , we may write the alarm clock to tape 4,
and simulate it until f(|x|) step, if “yes” then “yes” else “no”.
Lemma1 : Hf !in TIME(f([n/2]))
Proof :
Df(M) : if MHf(M;M) = “yes” then “no” else “yes”
What is Df(Df) ?
If Df(Df) = “yes”
=> MHf(Df;Df)=”no”
=> Df(Df) doesn’t accept within f(n)
=> Df(Df) =”no” ><
If Df(Df) = “no”
=> MHf(Df;Df)=”yes”
=> Df(Df) accept within f(n)
=> Df(Df) =”yes” ><
Lemma2 : Hf in TIME(f^3(n))
Proof :
Idea : Construct an 4-string Universal TM Uf with four strings that
simulate and decide Hf in O(f^3(n))
Time Hierarchy Theorem : TIME(f(n)) != TIME(f(2n+1)^3)
Proof : by Lemma1 and Lemma2
Collary : P != EXP
NSPACE(f(n)) in TIME(k^log(n)+f(n))
Proof :
Space Hierarchy Theorem : SPACE(f(n)) != SPACE(f(n)log(f(n)))
Proof :
Chapter 8 Reduction and Completeness
Reduction : L1 is reducible to L2 iff x in L1 <=> R(x) in L2
example 1: HAMILTON PATH≦r SAT
xij : node j is the ith node in the Hamilton path
1. node j must appear in the path : (x1j|x2j|..|xnj)
2. some node must be the ith : (xi1|xi2|..|xin)
3. node j cannot appear both in jth and kth : (-xij|-xkj)
4. node two node should be the ith : (-xij|-xjk)
5. if (i,j) !in E then I doesn’t follow j : (-xki|-xk+1,j)
Chapter 9 NP-complete problem
R(Σ*,Σ*) be an binary relation on strings .
Polynomial decidable (R) :
TM M s.t M(x,y)="yes" iff R(x,y)=True
Polynomial balanced (R) :
R(x,y) => |y| ≦ |x|^k
Proposition 9.1 :
L in NP iff R s.t L = {x: R(x,y) for some y}
Chapter 10 coNP and function problem
VALIDITY : Given φ, is x φ(x) = 1 ?
Lvalidity = Lsat'
Lsat in NP , so Lvalidity in coNP
Theorem : VALIDITY is coNP complete
Proof : if L in coNP then L' in NP,
R
so Ml'(x) ----> Msat(φ) , where φ=R(x)
let R'(x) = -R(x), then
Ml(x) = -Ml'(x) = -Msat(R'(x)) = Mvalidity(R(x))
and SAT is NP complete, so VALIDITY is coNP complete.
Proposition : if L is NP-complete then L' is coNP complete
Proposition : if L is NP-complete and L in NP then NP=coNP
RE ∩ coRE = Recursive
NP ∩ coNP =? P
Pratt's Theorem : PRIMES in NP ∩ coNP
Proof : by duality
Theorem(質數與殘餘的關係):
Prime(p) iff r {(1<r<p)&(mod(r^(p-1),p)=0)}
& q (mod(p,q)=0 & mod(r^(p-1)/q,p)=1)
ie : Prime(p) iff r residue(r) & exponent(r) = p-1
(where r is called a primitive root of p, every prime p has several r)
PRIMES in coNP :
Proof
Prime(p) iff q (1<q<p)&(mod(p, q)≠0) ,
so if there is a disqualification s.t
mod(p, q)=0 then !Prime(p)
PRIMES in NP :
Proof
1. We can calculate r^(p-1) mod p in O(log^3(max(r,p)))
2. C(p) = (r; q1,...,qk) where mod(p, qi)=0 and Prime(qi)
we can calculate C(p) in O(4log^2(p))
3. we can check C(p) in O(log^3(p))
New Symbol
m|n ==> mod(n,m)=0
(m,n) ==> gcd(m,n)=1
φ(n) : Euler function of n , φ(n) = {m : 1≦m<n, (m,n)=1}
Collary : φ(p) = p-1
Lemma1 : φ(n) = n Π (1-1/p)
p|n
Collary : if (m,n) = 1 then φ(mn) = φ(m)* φ(n)
Proof :
φ(mn) = mn Π (1-1/p) = m Π (1-1/p) * n Π (1-1/q)
p|mn p|m q|n
(because p|mn => p|m or p|n but not both)
Collary : if n = p1*p2*...*pk where pi≠pj for i≠j
then φ(n) = (p1-1)*(p2-1)*...*(pk-1)
Proof :
n* Π (1-1/pi) = p1*p2*...*pk*(1-1/p1)*(1-1/p2)*...*(1-1/pk) = (p1-1)*...*(pk-1)
1≦i≦k
韓信點兵問題: mod(x,3)=2 , mod(x,5)=3 , mod(x,7)=2 ,求最小的 x 為何數?
先求 :
mod(x1,3)=2 mod(x1,5)=0 mod(x1,7)=0
==> x1 = 3y1+2 = 5y2 = 7y3 5*7*2 mod 3 = 1
so x1 = 5*7*2 = 70
mod(x2,3)=0 mod(x2,5)=3 mod(x2,y)=0
==> x2 = 3y1 = 5y2+3 = 7y3 3*7 mod 5 = 1
so x2 = 3*7 = 21
mod(x3,3)=0 mod(x3,5)=0 mod(x3,7)=2
==> x3 = 3y1 = 5y2 = 7y3+2 3*5 mod 7 = 1
so x3 = 3*5 = 15
2x1+3x2+2x3 = 2*70+3*21+2*15 = 233 satisfy it
x=233 + i * 105 satisfy it , so 23 is the smallest positive
number satisfy it.
The Chinese Remainder theorem (中國剩餘定理)
n = Π pi
1≦i≦k
xi s.t (xi = 1 mod pi) and (xi = 0 mod pj) j≠i
let x = Σ ai*xi
1≦i≦k
mod(x,pi) = ai , 1≦i≦k
Collary :
n = Π pi , ri is primitive root of pi
1≦i≦k
then there is a unique r in φ(n) where
mod(r,pi) = ri
Lemma2 : Σφ(m) = n
m|n
Rewrite
Let Π pi^ki be the prime factorization of n ,
then Π pi^ki = n
1≦i≦a
Proof
suppose n = pi^ki, then
Π (φ(1)+ φ(pi)+...+ φ(pi^ki))
1≦i≦a
= [1+(pi-1)+(pi^2-pi)+...+(pi^k-pi^(k-1))]
= Pi^ki = n
so Π pi^ki = n
1≦i≦a
Fermat Theorem : For all 0<a<p, mod(a^(p-1),p)=1
Proof :
a*φ(p) = {mod(a*m,p)| m in φ(p)}
a*φ(p) = φ(p)
so when we multiply every number of both side
Πa*φ(p) = Πφ(p)
so mod(a^(p-1)*(p-1)!,p) = mod((p-1)!,p)
mod((a^(p-1)-1)*(p-1)!, p) = 0 , but gcd(p-1!, p)=0
so mod(a^(p-1)-1,p)=0
ie, mod(a^(p-1),p) = 1
Euler Theorem : for all a in φ(p) , mod(a*φ(p),p) = 1
Not all elements in φ(p) are primitive root
define : exponent : the least integer k > 0 s.t m^k = 1
Example :
φ(11) = {1,2,...,10}
mod(3^5,11) = 1 , so 3 is not primitive root, exponent(3)=5
mod(10^2,11) = 1, so 10 is not primitive root, exponent(10)=2
power of primitive map r^{1..p-1} 1-1 onto {1..p-1}
2^{1..10} = {2, 4, 8, 5, 10, 9, 7, 3, 6, 1}
R(k)=the total number of residues in φ(p) that has exponent k
Property : R(k) = 0 iff mod(p-1, k) ≠ 0
(因所有的 exponent(r) 都是 p-1 的因數--by mod(a^(p-1),p)=1)
Question : What's the maximum value of R(k)
Lemma3 : Any polynomial of degree k that is not identically zero has at most k distinct roots modulo p.
Property 3.1 :
R(k) ≦ k (1, s, s^2, ..., s^(k-1))
are all distinct root of x^k =1 mod p
Property 3.2 :
R(k) ≦φ(k)
if s^i have exponent k then i in φ(k) , so R(k) ≦φ(k)
Theorem : p-1 ≦ Σ R(k) ≦ Σφ(k) = p-1
k|p-1 k|p-1
Proof : p-1 ≦ Σ R(k), because all p-1 residue have an exponent
k|p-1
Σ R(k) ≦ Σφ(k), because of Property 3.2
k|p-1 k|p-1
Σφ(k) = p-1, because of Lemma 2
k|p-1
So , R(k) = φ(k) for all divisor of p-1
and R(p-1) = φ(p-1) > 0, so p has at least one primitive root
r^φ(p) = 1 mod p
if p is not prime then
φ(p) < p-1
let k be the smallest k s.t r^k=1 mod p ,
then k|φ(p) and k|p-1
let q be the prime divisor of (p-1)/k
then r^((p-1)/q) = r^(ak) = 1 mod p.
so , Residue Theorem Hold.
Function Problem
FSAT(φ) : if φ is satisfiable then Given a truth assignment T(x)
else say "no"
Theorem : if SAT(φ) in P then FSAT(φ) in P
Proof :
FSAT(φ, T[1..|x|])
if (SAT(φ)= "no") return "no"
if (i < |x|)
if (SAT(φ(xi=1)) then
T[i] = 1
FSAT(x[xi=1])
else
T[i] = 0
FSAT(x[xi=0])
else
return T
Theorem : FP = FNP iff P = NP
Theorem : FSAT is FNP-complete
Theorem : NP-complete ≦ FTSP
(because we don't know how to verified a solution is optimal or not in polynomial time.)
FL : Given x, if y RL(x,y) return y else return "no"
Function Problem Reduction (FR):
FR
A -----> B :
where R,S in LOGSPACE
A(x) --> B(R(x))
S(z)=B(R(x)) --> z=A(x)
R is a TFNP(total FNP) problem iff x y R(x,y)
FACTORING Problem :
Decompose N into it's primitive product N=p1^k1*p2^k2*...*pm^km
Is FACTORING problem an NP complete problem ?
(this is an open problem)
FACTORING problem is TFNP
HAPPYNET problem :
Chapter 11 Randomized Computation
Given a graph G, there is a adjacent matrix A represent G
det A = Σσ(π)Π A(i,π(i)) -- definition
π 1≦i≦n
example : 2*2 的矩陣之 determinent
π = (1, 2) (2, 1)
a11 a12
|a21 a22| = -1^0 a11a22 + -1^1 a12a21 = a11a22-a12a21
example : 3*3 的矩陣之 determinent
π = (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
a11 a12 a13
|a21 a22 a23| = -1^0 a11a22a33 + -1^1 a11a23a32 + -1^1 a12a21a33
a31 a32 a33 + -1^2 a12a23a31 + -1^2 a13a21a32 + -1^1 a13a22a31
= a11a22a33 + a21a32a13 + a31a23a12
- a13a22a31 - a12a21a33 - a11a32a23
Symbolic Matrix :
Example :
x w z x w z
z x w => 0 (x^2-zw)/x (wx-z^2)/x
y z 0 0 (zx-wy)/x -zy/x
x w z
=> 0 (x^2-zw)/x (wx-z^2)/x
0 0 -yz(xz-xw)+(zx-wy)(wx-z^2)/x(x^2-zw)
Only nonzero term in this sum are those that correspond to perfect matching π in G
Gaussian elimination (GE):
1. if A is a number matrix : GE can be used to compute |A| in polynomial time.
2. if A is a symbolic matrix : GE will make the diagonal exrpression exponential long.
Even talling whether a specific monomial (like x^2zw) in the determinent with a nonzero coefficient is NP-complete
Bipartite Perfect matching problem
Given a bipartite graph G, does G has a perfect matching ?
↓R
Symbolic Matrix Determinent problem
Given a symbolic matrix A(x1,..,xm), is |A(x1,..,xm)| = 0 ?
G has a perfect matching <==> |A| ≠ 0
Monte Carlo algorithm :
A Monte Carlo algorithm to test whether G has a perfect matching :
HasMatching(G(V,E))?
transform G into it's adjacent matrix A(x1,..,xn)
(Aij = xij iff (ui,vj) in E
= 0 iff (ui,vj) not in E)
A(x1,..,xm) 隨便 assign x1,..,xn 一組值(c1,..,cm)
,用 GE 計算矩陣的 determinent,
(0≦ci≦M = 2m)
if A(c1,..,cn) ≠ 0
then say "G has a perfect matching"
else say "G probably has no perfect matching"
Lemma :
let π(x1,...,xm) be a polynomial, π(x1,...,xm)≠0,
each variable degree at most d,
then |{(x1,...,xm)| π(x1,...,xm)=0}| ≦ mdM^(m-1)
Proof :
for m = 1, π(x1)=0 has at most 1*d*M^0 = d is true
(d 次多項式最多有 d 個根)
Random Walk (φ, r):
Randomize a solution T
for i=1 to r do
if yes
return “YES”
else
flip an element in solution T
return “this problem is probably unsatisfiable”.
Theorem : random walk 2SAT became monte carlo.
if 2SAT φ is satisfiable, then
P(RandomWalk(φ, 2n^2 times)=”yes”) > 1/2
Proof
T’ : T’(φ) = True
T : differ from T’ in exactly i value.
t(i)≦ 1/2 (t(i-1)+t(i+1)) + 1
t(0) = 0, t(n) ≦ t(n-1) + 1
the solution of
x(i)= 1/2 (x(i-1)+x(i+1)) + 1
x(0)=0, x(n) = x(n-1) + 1
is 2*i*n-i^2
Chebshyv inequality : P(x≧kE(x)) ≦ 1/k*E(x)
Proof
E(x) = Σi*Pi = Σi*Pi + Σi*Pi > k*E(x)P(x>kE(x))
i i≦kE(x) i>kE(x)
x(n) = n^2, so E(x) < n^2
so P(x ≧ 2n^2) < P(x>2E(x)) < 1E(x)/2E(x) = 1/2
so when r = 2n^2 , the 2SAT random walk became an monte carlo
A Monte Carlo algorithm to solve primality
Carmichael number : N = p1*p2*..Pn, pi-1|N-1 for all I
Lemma : if a^(p-1)/2 = 1 mod p then x^2 = a mod p has 2 roots
if a^(p-1)/2≠1 mod p then x^2 = 1 mod p has no roots
x^2 =-1 mod p has no roots
Legendre symbol : (a|p) => a^(p-1/2) mod p in {1, -1}
Lemma : (ab|p) <=> (a|p)(b|p)
Residue(r) : r^(p-1) = 0 mod p
Recall that : Prime(p) iff r residue(r) & exponent(r) = p-1
Prime(p) iff r {(1<r<p)&(mod(r^(p-1),p)=0)}
& q (mod(p,q)=0 & mod(r^(p-1)/q,p)=1)
ie : Prime(p) iff r residue(r) & exponent(r) = p-1
(where r is called a primitive root of p, every prime p has several r)
Gauss’s Lemma
(q|p) = -1^m m = |R╞|{x|x = i*q mod p and x > (p-1)/2 }|
(both p, q are primes)
Proof
1. i≠j => iq ≠ jq,
Proof :
if (i-j)q mod p = 0 then i-j mod p = 0 or q mod p = 0 ><
2. i≠j => iq + jq ≠ 0
Proof :
if (i+j)q mod p = 0 then i+j mod p = 0 or q mod p = 0 ><
define R’={if iq mod p ≦ p-1/2 then iq mod p else p-iq mod p}
Assert : |R'| = p-1/2
Proof :
if (p-i = jq mod p) then iq+jq mod p = 0 ><
R’ mod p = {±q, ±2q, .., ±(p-1)q/2} = {1,2, .., p-1/2}
and R’ has exactly m element with negative sign
so
so (p-1/2)! = (-1)^m*q^(p-1/2)*(p-1/2)! Mod p
but (p-1/2)! Cannot divide p, so (-1)^m*q^(p-1/2) mod p = 0
q^(p-1/2) = (-1)^m mod p .
Legendre’s Law of Quadratic Reciprocity
(p|q)*(q|p) = (-1)^( p-1/2 * q-1/2 ) (both p, q are primes)
Proof :
R’ mod p = {±q, ±2q, .., ±(p-1)q/2} = {1,2, .., p-1/2}
Σiq mod p = Σi mod 2
1≦i≦p-1/2
q*Σi - pΣiq/p + mp = (p-1)(p+1)/8 mod 2
(because 1. iq , 2. took residue 3.p-i )
= (p-1)(p+1)/2 mod 2
(because p-1, p+1 is even)
q*(p-1)(p+1)/2 - pΣiq/p + mp = (p-1)(p+1)/2 mod 2
pΣiq/p + mp = 0 mod 2 (because q*(p-1)(p+1) = p-1 mod 2)
pΣiq/p = mp mod 2
Geographically
The Class RP (randomize polynomial) and Monte Carlo Algorithm
L in R(P(|x|)) iff M accept L by majority and reject unanimously
ie: M x in L => |{path| M(x, path) = “yes” }| > 2^P(|x|)/2
x !in L => M(x) = “no”
L’ in coR(P(|x|)iff M reject L by majority and accept unanimously
ie: M x in L => M(x) = “yes”
x !in L=> |{path| M(x, path) = “no”}| > 2^P(|x|)/2
RP = ∪ R(|x|^i) coRP = ∪ coR(|x|^I)
i i
Theorem : Given RTM Mr, is Mr a RTM that accept L Monte Carolly is a undecidable problem.
The Class RP (randomize polynomial) and Monte Carlo Algorithm
ZPP = RP ∩ coRP
A LasVegas Algorithm that accept L and reject L’
Mz(x) : loop
if Mr(x) = “no” then return “no”
if Mcor(x) = “yes” then return “yes”
forever
Monte Carlo Algorithm :
若say “no” 則x !in L, 若say “yes” 則P(x in L) ≧ 0.5
Las Vegas Algorithm :
if stop then answer correct , but may loop many times
with reverse exponent probability.
Syntactic Class : 有辦法判斷一給定的答案是否是certificate.
Ex : P, NP,.. (有complete class)
Semantic Class : 沒有辦法判斷一給定的答案是否是certificate.
Ex : RP, coRP, PP, .. (沒有complete class)
Standard Complete Language {(M,x): M inMand M(x) = “yes”}
The Class PP and PP-complete:
L in PP(P(|x|)) iff
NTM M,if M accept x by majority then x in L else x !in L
MAJSAT Problem :
Given Boolean Expression φ(x1,..,xn), is |{T|T(φ)=True}|>2^(n-1)
Theorem : MAJSAT is PP-complete
Proof :
↗NTM M -> M(x)
x ->
↘NTM M -> “yes”
Complexity Hierarchy :
in RP in NP
P in ZPP in BPP in PP
in coRP in coNP
Chapter 12 Cryptography
One way function f:
1. f is 1-1 and x inΣ*,|x|^1/k ≦ |f(x)| ≦ |x|^k for some k
2. f in FP
3. f-1 !in FP
RSA的另兩個特性:
1. trapdoor function :
fRSA(x,e,p,c(p),q,c(q)) 有一定比例不是Undefine (是defined)
2. d(x) in P, f(d, fRSA(x, e)) = x
Class UP (unambiguous nondeterministic polynomial)
x |{path | M(path, x) = “yes” }| ≦ 1
Theorem : UP = P iff there are no one way function
Signature :
S(x) = (x, D(d,x))
A -- S(x) -- > B – encrypt D(d,x) -- > E(D(d,x)) = x
B check is x = E(D(d,x)) ?
if “yes” then S(x) is send by A
otherwise S(x) may be a lie.
Commutative :
E(e, D(d,x)) = D(d, E(e,x))
Theorem : RSA encryption system is commutative
D(d, E(e,x)) = (x^e)^d mod pq = (x^d)^e mod pq = E(e, D(d,x))
Interactive Proof System (A,B):
x A –- m[1],.. , m[2|x|^k-1] -- > B x
< -- m[2],.. , m[2|x|^k] --
m[2i-1] = A(x, m[1], .. , m[2i-2])
m[2i] = B(x,m[1],..,m[2i-1])
m[2|x|^k] in {“yes”, “no”}
m[I] ≦ |x|^k
(A,B) decide L iff
if x in L then P((A ,B) accept x) ≧ 1-(2^-|x|)
if x !in L then P((A’,B) accept x) ≦ 2^-|x| , for all A’≠A
Class IP :
x in IP => x decide by some interactive proof system (A,B)
NP in IP
BPP in IP
Theorem : Graph Nonisomorphizm in IP
Proof :
-- m[1] = (G,G’) -------------->
A <-- m[2i-1]=(G, Πi(Gi)) ------ B
-- m[2i]= isIso(G, Πi(Gi)) --->
Πi(Gi) : if b[i] = 1 then G else G’
if (isIso(G,G’))
then m[2] = .. = m[2|x|] = 1
else if m[2] = b[1], .., m[2|x|] = b[|x|]
then B accept it (return iso(G,G’))
else B reject it (don’t believe iso(G,G’))
Chapter 13 Approximability
F(x) : feasible solution instance set.
OPT(x) = minx in F(x)c(s) for minimization problem
= maxx in F(x)c(s) for maximization problem
εapproximation algorithm :
M is anεapproximation algorithm iff x
|c(M(x))-OPT(x)|/max{OPT(x), c(M(x))} ≦ ε
Approximation threshold for A: greatest lower bound of εfor A
Theorem :
1. The lower bound of k-MAXGSAT is at most 1-1/2^k
2. The lower bound of MAXSAT is at most 1/2
3. The lower bound of MAXSAT with k distinct literal is at most 1/2^k
Theorem : NP-complete = R Hamilton <R TSP(1-ε)
Proof :
G = (V,E)
dist(u,v) =
if (u,v) in E
then dist(u,v) = 1
else dist(u,v) = |V|/(1-ε)
so :
TSP(dist) has (1-ε) approximation threshold iff Hamilton in P
Theorem : The approximation threshold of KNAPSACK is 0.
(ε>0 there is a polynomial approximation algorithm for KNAPSACK)
Proof :
dual problem : W(i+1,v) = min{W(i,v), W(i,v-vi+1)+Wi+1}
S=(v1,.., vn) truncate b bit -> (v1’,..,vn’)=S’
Σvi ≧ Σvi ≧ Σvi’ ≧ Σvi’ ≧ Σ (vi-2^b) ≧ Σvi-n*2^b
i in S i in S’ i in S’ i in S i in S i in S
let ε = n*2^b/V => b = log(εV/n)
(R,S) is L-Reduction from A to B iff
OPT(R(x)) ≦ α*OPT(x), where x in A, R(x) in B
|OPT(x) - c(S(s))| ≦ β*|OPT(R(x))-c(s)| , where s in R(x)
Theorem : L-reduction is transitive
A -(R,S)-> B -(R’,S’) -> C
A -------(RR’,SS’)-----> C
Theorem : if A - (R(α),S(β)) -> B, and εapproximate for B then
αβε/(1-ε) approximate for A
Proof :
x in A, y in B
OPT(R(x)) ≦ α*OPT(x)
c(M(R(x)))
Post preview:
Close preview