推 k6416337 :八卦版有最新發展了 08/11 20:50
推 hcsoso :finite model theory 沒有學過... 08/11 20:58
http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
有興趣先建議看這篇，現在有看完而且看懂的人不多，
但是這篇先講了一下證明的策略。先將 P class 用
邏輯來描述：
Theorem: On ordered structures, a relation is defined by a first order
formula plus the Least Fixed Point (LFP) operator if and only if it is
computable in polynomial time.
LFP 在 ordered structures 上就是找函數的固定點算子，
對一個 PX 上的函數 F : PX --> PX 可以定義
F^0 = 空集合，F^{n + 1} = FF^{n}
若序列 (F^{n}(X)) 是遞增的，那麼必定會有最小固定點。
證明不難，從空集合開始往上爬，將 F 的定義延伸到 limit ordinal
套用 set 跟 class 的大小不同，就得到了。
接下來他就直接進攻 SAT ...
※ 引述《lwei781 (會乖 會聽話)》之銘言：
: http://www.scribd.com/doc/35539144/pnp12pt
: 很長.....
: 要找時間才能讀
: http://rjlipton.wordpress.com/
: comments
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 82.36.219.50