中级农民
- 积分
- 116
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2009-6-16
- 最后登录
- 1970-1-1
|
基本有定论了
http://rjlipton.wordpress.com/20 ... -deolalikars-proof/
Fatal Flaws in Deolalikar’s Proof?
Terence Tao. 1point 3 acres
August 13, 2010 2:13 am. check 1point3acres for more.
Neil’s critique does seem to align quite consistently with the consensus that we had just been reaching today, that the problems with the argument are originating from the finite model theory component of the argument and then being indirectly detected also at the random SAT and complexity theory side of things. With reference to the three levels of questions from the previous thread, it seems we can now answer both question #1 and question #2 as a definite “No.”.
The status of question #3 still seems to me, though, to be a more equivocal “Probably not”. Ryan’s examples demonstrating how solution space structure seems to be almost decoupled from worst case complexity is admittedly rather compelling, but there could still _conceivably_ be an elusive “Property A” that is obeyed by solution spaces to easy problems (possibly after a reduction), but is not obeyed by a standard problem suspected to be difficult, such as k-SAT, thus splitting a complexity separation task into the Claim 1 and Claim 2 components discussed previously (provided that reduction issues are dealt with properly). While it is now clear that the type of finite model theory tools being deployed in the Deolalikar paper are not powerful enough by themselves to handle Claim 1, it could still be that there exists a reasonable candidate for Property A along the lines of the “polylog-parameterisable” intuition of Deolalikar for which Claim 1 and Claim 2 could still be conjecturally true for some complexity separation problem (perhaps one weaker than P != NP, but still nontrivial). While Ryan’s examples (and also, to some extent, the natural proofs barrier) are certainly significant obstructions to this occuring (and the whole SAT/XORSAT business would also significantly obstruct any attempt to prove the Claim 2 side of things), perhaps there is still some loophole that may offer a way to salvage the strategy at least of Deolalikar’s argument, if not an actual result? |
|