# 訊息

## English

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