# 訊息

## 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)```
```