Complexity

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

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(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)))

Facebook

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