NP-Complete 問題

# 轉化 (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(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 :```
```