s***n
发帖数: 459 | 1 Lipton Blog今晚的更新(下午还没有)，乱翻译一下。
陶哲轩（菲尔兹奖得主，数学届希望之星，刚成立的5人验证小组成员）：
我觉得“这个证明正确吗？”这个基本问题有好几重含义：
1.Deolalikar的证明，经过一些小的修改，是否能证明P不等于NP？
2.Deolalikar的证明，经过一些重大修改，是否能证明P不等于NP？
3.Deolalikar的证明思路（探究随机k-SAT中的独立性特征）是否
有希望导致任何非平凡的计算复杂度分类方面的结果？
经过各方联合努力，现在对#1的答案（虽未完全确定）看来是“否”
（参见wiki文档），对#2目前最好的答案是“可能不成立,除非再引入
别的重大新思想。”但我觉得#3仍未完全解决，而且值得继续追究
（尽管不会再是前几天那种狂热的互联网速度）。
Terence Tao:
I think there are several levels to the basic question “Is the proof
correct?”:
1.Does Deolalikar’s proof, after only minor changes, gi |
p**********0
发帖数: 101 | 2 这个问题会不会象《连续统假设》问题一样？其数学公理化定义不清？如是，该证明多
半站不住。 |
s***n
发帖数: 459 | 3 有这种猜测。
另外，“康托连续统假设的数学公理化定义不清”，是个严肃的结论还是也是猜测？
【在 p**********0 的大作中提到】
: 这个问题会不会象《连续统假设》问题一样？其数学公理化定义不清？如是，该证明多
: 半站不住。
|
l******e
发帖数: 470 | 4 你看看这篇
http://www.scottaaronson.com/papers/pnp.pdf
这个问题要象连续统一样是独立的，也是要证明的，要是证明出来了，也基本说明这个
问题基本被搞定的，不用在忙活着证等于还是不等于了，除非换公里
【在 p**********0 的大作中提到】
: 这个问题会不会象《连续统假设》问题一样？其数学公理化定义不清？如是，该证明多
: 半站不住。
|
b***u
发帖数: 12010 | 5 没看懂证明，不过那个blog上说这个方法可以推出2SAT也不是P，这显然不对，所以有
问题。基本结论是证明不对，但这个方向有没有重大意义还在研究。 |
D***h
发帖数: 183 | 6 基本上没有可能成立了
http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/
Terence Tao
August 13, 2010 2:13 am
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
previou
【在 b***u 的大作中提到】
: 没看懂证明，不过那个blog上说这个方法可以推出2SAT也不是P，这显然不对，所以有
: 问题。基本结论是证明不对，但这个方向有没有重大意义还在研究。
|
t******e
发帖数: 1293 | 7 原来biggu也是搞CS的啊
【在 b***u 的大作中提到】
: 没看懂证明，不过那个blog上说这个方法可以推出2SAT也不是P，这显然不对，所以有
: 问题。基本结论是证明不对，但这个方向有没有重大意义还在研究。
|
j******w
发帖数: 690 | 8 这个要看你相对于哪个公理系统。
如果是相对于PA(Peano axioms)证明PvsNP的独立性还有可能。但是这个基本也是毫无
进展。很多
搞证明论的试图在PA的极弱的子公理下证明PvsNP的独立性都没有成功。
如果是相对于ZFC就麻烦了。ZFC对于表述简单的命题有个绝对性原理。这本来对于证明
是件好事
情。但是如果这类简单的命题是独立于ZFC的，那么它的独立性都不可证。也就意味着
不能像
Cohen那样用个forcing 就造出来了。也许Pvs NP就是个大基数公理也说不定。
【在 l******e 的大作中提到】
: 你看看这篇
: http://www.scottaaronson.com/papers/pnp.pdf
: 这个问题要象连续统一样是独立的，也是要证明的，要是证明出来了，也基本说明这个
: 问题基本被搞定的，不用在忙活着证等于还是不等于了，除非换公里
|
