NP-Complete 問題

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

轉化 (Reduction)

A is reducable to B iff there exists a total computable function t such that for any x,
in set A iff t(x) in set B

NP-Complete 定理

NP-complete Theorem (Cook)
The problem of stating the satisfiability of propositional formulas in conjunctive
normal form is NP-complete.

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 :

Facebook

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