我沒辦法在八卦板 po
可是大家真的不要繼續被 deolalikar 整了
他是來鬧的
該欣賞的是他怎麼有辦法鬧到這麼多人
直接去他網站讀他的 paper
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf
看他 P vs. NP 證明：
Theorem 8.10 第 99頁開始
證明理第三句就錯了
“The first observation we make is that since the variables in cores are instantiated in exponentially many clusters, we can preclude value limited poly(log n)-parametrization.”
XORSAT 是 counter example
整偏前面放一大堆抄來的數學只是在讓證明模糊
希望大家不會直系看
不管有沒有背景如果你仔細讀他 Theorem 8.10 證明
就很明顯他是來搗亂的
※ 引述《xcycl (XOO)》之銘言：
: 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: 71.132.143.80