計算理論 -- 複雜度簡介

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

Given a proof theory, It should be

sound : it only proves "true" thing
complete : it can prove everything that's true.
Computer => Efficient

Most proving search time is undecidable, so we cannot compare which one is more efficient .

The search complexity for propositional logic is co-NP complete.

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)

Facebook

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