隨機複雜度 (Randomize Computation)

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

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 .

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

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License