Complexity

# 訊息

## English

``````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(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 .

(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 inＭand 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,.. , m[2|x|^k-1] -- > B  x
< -- m,.. , m[2|x|^k]    --

m[2i-1]         = A(x, m, .. , m[2i-2])
m[2i]        = B(x,m,..,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 = (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 = .. = m[2|x|] = 1
else if m = b, .., 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)))```
```