t*********l
发帖数: 566 | |
g*****g
发帖数: 34805 | 2 Wow, really? That's really a breakthrough if true.
【在 t*********l 的大作中提到】
: HP lab的一个研究员。
|
K****n
发帖数: 5970 | |
v******d
发帖数: 1322 | 4 http://www.hpl.hp.com/personal/Vinay_Deolalikar/
【在 g*****g 的大作中提到】
: Wow, really? That's really a breakthrough if true.
|
v********e
发帖数: 1058 | 5 真depressing..
【在 t*********l 的大作中提到】
: HP lab的一个研究员。
|
w**********s
发帖数: 291 | 6 不知道几个人看得懂啊，横跨若干大领域。
这人不像民科，所以还真说不定提出了一些新颖的想法。 |
f*****x
发帖数: 2748 | |
m****s
发帖数: 402 | 8 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
【在 t*********l 的大作中提到】
: HP lab的一个研究员。
|
a****9
发帖数: 418 | 9
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ P \subseteq NP
【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
|
w**********s
发帖数: 291 | 10 不管结果怎么样，能证出来，应该还是有新发现的。
一般来说，都要牵动多个领域，发展一些新的工具。
纯科学研究嘛，就包括满足好奇心。不到黄河心不死。
【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
|
|
|
a****9
发帖数: 418 | 11 再等等,
现在还只是他自己claim证出来了
要看其他人会不会挑出来错
【在 t*********l 的大作中提到】
: HP lab的一个研究员。
|
m****s
发帖数: 402 | 12 A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of re |
t******a
发帖数: 1200 | 13 1. P means polynomial time solvable, but NP doesn't mean non-polynomial.
NP means a solution to the given problem is verifiable in polynomial time.
So you mis-interpreted the meaning of N vs. NP at the first place.
2. Lance Fortnow's review, The Status of the P Versus NP Problem
(Communications of the ACM Vol. 52 No. 9, Pages 78-86 ), gives a good
and easy to follow explaination on why this question matters.
【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
|
t******a
发帖数: 1200 | 14 Richard J. Lipton (Professor in Computer Science at Gatech) wrote
a blog about this solution and generated a lot of serious comments
blew. So far the best place to check at this moment.
https://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
【在 t*********l 的大作中提到】
: HP lab的一个研究员。
|
a****9
发帖数: 418 | |
l*****8
发帖数: 16949 | 16 你的理解错误。
P表示一个问题有一个确定性的算法，用多项式时间可以计算。
NP表示一个问题有一个不确定的解法（也就是说可能有10000种可能的解法，这里面至
少有一个解法是正确的），如果你蒙对了的话，那么也是只要多项式时间可以算出。如
果你不蒙，一个一个解法试下来的话就不是多项式时间可以解决的了。
PS:上面的10000只是一个比方,实际的可能解法和输入有关。
比方说，分解一个两素数的乘积 n=p*q。如果是确定性算法，你可能就要从2,3,5,7,..
.一个个素数除过来，最坏情况要一直除到 n^1/2。可是如果是不确定算法，那你可以
随便挑一个1~n^1/2之间的数。如果你蒙对了，那么一步就算出来了。所以确定性算法
通常比非确定性算法更费时间。但要从理论上证明则是非常难得。
【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
|
a****9
发帖数: 418 | |
l*****8
发帖数: 16949 | 18 用一个不太严格的比方，RSA算法的基础是分解两个素数需要的时间是NP问题，但不是P
问题。对知道密钥的来说只要多项式时间就能分解，对不知道密钥的来说是个NP问题，
如果想多项式时间算出，就只能蒙。RSA的基础就是假设不存在一个确定性的算法在多
项式时间内可以分解素数的乘积。
如果P=NP的话，那么所有NP问题就能转化为P问题，公开密钥系统就马上崩溃了。 |
w****o
发帖数: 2210 | 19 这儿有很多comments：
http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
甚至连YANG Zheng-Ling老人家都说话了：
YANG Zheng-Ling permalink
August 9, 2010 9:05 am
I believe that “P is not equal to NP”.
Maybe I have proved it in 1993~1995. |
X*****r
发帖数: 2521 | 20 what is this?
【在 w****o 的大作中提到】
: 这儿有很多comments：
: http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
: 甚至连YANG Zheng-Ling老人家都说话了：
: YANG Zheng-Ling permalink
: August 9, 2010 9:05 am
: I believe that “P is not equal to NP”.
: Maybe I have proved it in 1993~1995.
|
|
|
d********f
发帖数: 43471 | 21 Rafee Kamouna permalink
August 9, 2010 10:43 am
This proves:
P=NP iff P!=NP.
【在 w****o 的大作中提到】
: 这儿有很多comments：
: http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
: 甚至连YANG Zheng-Ling老人家都说话了：
: YANG Zheng-Ling permalink
: August 9, 2010 9:05 am
: I believe that “P is not equal to NP”.
: Maybe I have proved it in 1993~1995.
|
m****s
发帖数: 402 | 22 P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
数学要这样的话，是不是1!=2也要证。
..
【在 l*****8 的大作中提到】
: 你的理解错误。
: P表示一个问题有一个确定性的算法，用多项式时间可以计算。
: NP表示一个问题有一个不确定的解法（也就是说可能有10000种可能的解法，这里面至
: 少有一个解法是正确的），如果你蒙对了的话，那么也是只要多项式时间可以算出。如
: 果你不蒙，一个一个解法试下来的话就不是多项式时间可以解决的了。
: PS:上面的10000只是一个比方,实际的可能解法和输入有关。
: 比方说，分解一个两素数的乘积 n=p*q。如果是确定性算法，你可能就要从2,3,5,7,..
: .一个个素数除过来，最坏情况要一直除到 n^1/2。可是如果是不确定算法，那你可以
: 随便挑一个1~n^1/2之间的数。如果你蒙对了，那么一步就算出来了。所以确定性算法
: 通常比非确定性算法更费时间。但要从理论上证明则是非常难得。
|
w****o
发帖数: 2210 | 23 1+1 =2 不是需要证明的么
【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
|
l****u
发帖数: 4594 | 24 我怎么觉得，你说的没一个对的？
【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
|
w***n
发帖数: 1084 | 25 You didn't get it and someone explained it in such a complicated way.
给你一个问题，
P的意思是：从０开始找到这个问题的答案的时间是polynomial
time.
NP的意思是：假如某人告诉你一个答案，你去验证这个答案对不对的时间是
polynomial time.
P显然是NP的。因为polynomial的时间里你把答案都找出来了，要验证还不是直接比较
以下就得了？
但NP是不是P, 这个才是问题。
【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
|
l*****8
发帖数: 16949 | 26 No. 2^N这样的复杂度通常称为EXP (exponential),或者叫指数复杂度。
P<=NP<=EXP.第一个可以去掉等号如果这个证明是正确的。但NP未必等于EXP.
P
NP
事实上这个一点都不明显。比如 PSPACE 和 NPSPACE就是相同的.也就是说如果只以占
用存储的大小来衡量复杂度的话，P和NP是相同的。通常我们说的P和NP是用时间来衡量
复杂度的。
另外，O(N)叫线形时间，多项式时间是O(N)+O(N^2)+O(N^3)+.....
2^N是exp问题。
【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
|
m*****u
发帖数: 19562 | 27 你解释的太复杂了。
【在 l*****8 的大作中提到】
: No. 2^N这样的复杂度通常称为EXP (exponential),或者叫指数复杂度。
: P<=NP<=EXP.第一个可以去掉等号如果这个证明是正确的。但NP未必等于EXP.
: P: NP: 事实上这个一点都不明显。比如 PSPACE 和 NPSPACE就是相同的.也就是说如果只以占
: 用存储的大小来衡量复杂度的话，P和NP是相同的。通常我们说的P和NP是用时间来衡量
: 复杂度的。
: 另外，O(N)叫线形时间，多项式时间是O(N)+O(N^2)+O(N^3)+.....
: 2^N是exp问题。
|
s******g
发帖数: 3841 | 28 你根本没懂P和NP的定义
建议你先去wiki科普一下
推荐你看一本日本侦探小说叫嫌疑犯x的献身，里面用破案给P和NP打了一个比方，很有趣
【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
|
a****9
发帖数: 418 | 29 你这对P,NP的理解根本就是错的,
我发现不少人(甚至包括不少cs科班出身的)望文生义的以为
P就是polynormial
NP就是non-polynormial
要我说 这名字确实也起的不好
面至
。如
7,
可以
算法
【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
|
Y*****y
发帖数: 361 | 30
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
应该说是deterministic和nondeterministic花的空间几乎是一样吧，因为前者可以在
不太多额外空间的条件下simulate后
者。
【在 l*****8 的大作中提到】
: No. 2^N这样的复杂度通常称为EXP (exponential),或者叫指数复杂度。
: P<=NP<=EXP.第一个可以去掉等号如果这个证明是正确的。但NP未必等于EXP.
: P: NP: 事实上这个一点都不明显。比如 PSPACE 和 NPSPACE就是相同的.也就是说如果只以占
: 用存储的大小来衡量复杂度的话，P和NP是相同的。通常我们说的P和NP是用时间来衡量
: 复杂度的。
: 另外，O(N)叫线形时间，多项式时间是O(N)+O(N^2)+O(N^3)+.....
: 2^N是exp问题。
|
|
|
l*****8
发帖数: 16949 | 31 是的，所以PSPACE=NPSPACE.不过严格的证明也不是很简单
【在 Y*****y 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 应该说是deterministic和nondeterministic花的空间几乎是一样吧，因为前者可以在
: 不太多额外空间的条件下simulate后
: 者。
|
l*****8
发帖数: 16949 | 32 是的。我再试着重新解释一遍：
P和NP涉及到两种不同的算法,确定性的和不确定性的。前者就是通常意义上的算法，算
完第一步怎么算下一步都是确定的，计算机程序基本都是确定性的算法。非确定性算法
则带有蒙的性质，就像走迷宫，走到某一步你可以有左，右，向前三种选择，下一步可
能又有三种选择。没人告诉你那条路可以出去。但肯定有一条路是通的。
P问题就是说有一个确定性的算法，用多项式时间可以算出答案。
NP问题就是说有一个类似迷宫算法，肯定有一条路（当然也可能有多条路)是通的，而
且如果你碰巧走了最短的路，那只要多项式时间就能走完。
所以P问题一定也是NP问题，因为确定性算法是非确定性算法的特例。任何一个非确定
性算法也可以用确定性算法来模拟：只要穷举每一条可能的路线就行了。但这种穷举方
法就不是多项式时间可以算完的了。
【在 m*****u 的大作中提到】
: 你解释的太复杂了。
|
r******l
发帖数: 10760 | 33 确实，无数人认为NP是Non Polynomial的缩写，肯定是上课时睡觉了。。。
【在 a****9 的大作中提到】
: 你这对P,NP的理解根本就是错的,
: 我发现不少人(甚至包括不少cs科班出身的)望文生义的以为
: P就是polynormial
: NP就是non-polynormial
: 要我说 这名字确实也起的不好
:
: 面至
: 。如
: 7,
: 可以
|
Y*****y
发帖数: 361 | 34 说反了？
不过这样说也不完全对。因为到目前为止还没人（这篇paper的结果暂时未定）证明一
定没有很efficient的search的办法…
search也不一定非要enumerate吧：）有点抓字眼了，不好意思。
search |
l*****8
发帖数: 16949 | 35 你的直觉很对。如果证明P=NP，只要能找到一个超级efficient的搜索算法就行了。问
题是这样的算法一般认为不存在。
【在 Y*****y 的大作中提到】
: 说反了？
: 不过这样说也不完全对。因为到目前为止还没人（这篇paper的结果暂时未定）证明一
: 定没有很efficient的search的办法…
: search也不一定非要enumerate吧：）有点抓字眼了，不好意思。
:
: search
|
Y*****y
发帖数: 361 | 36 呵呵，我的直觉是P!=NP。不然整个人类社会就彻底改变了，至少那些crypto的system
基本都废了。 不过我不是专门搞
complexity的，所以只有旁观的份。
【在 l*****8 的大作中提到】
: 你的直觉很对。如果证明P=NP，只要能找到一个超级efficient的搜索算法就行了。问
: 题是这样的算法一般认为不存在。
|
p*********g
发帖数: 226 | 37 不过我一直搞不懂，既然叫 non-deterministic polynomial, 那总有什么东东是
polynomial 的吧? |
s*********b
发帖数: 815 | 38 如果俺没有记错的话，假设一个NP问题可能解的集合是S，那么
您老同时调用|S|台图灵机，每台机器验证条可能解。这个算法肯
定是多项式的，问题是您老不知道哪台机器算出正确结果，所以它
是non-deterministic的。
【在 p*********g 的大作中提到】
: 不过我一直搞不懂，既然叫 non-deterministic polynomial, 那总有什么东东是
: polynomial 的吧?
|
b******e
发帖数: 432 | |
j*****n
发帖数: 1545 | |
|
|
d******e
发帖数: 7844 | 41 外行容易犯的错误.
【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
|
D***h
发帖数: 183 | 42 http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/
"Still there remains the key question: is the proof correct? In one sense
the present paper almost surely has mistakes—not just from the above
objections but what one could expect of any first-draft in a breakthrough
situation. The real questions are, is the proof strategy correct, and are
the perceived gaps fixable? " |
z*****n
发帖数: 7639 | 43 IT这话啥意思？
【在 w****o 的大作中提到】
: 这儿有很多comments：
: http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
: 甚至连YANG Zheng-Ling老人家都说话了：
: YANG Zheng-Ling permalink
: August 9, 2010 9:05 am
: I believe that “P is not equal to NP”.
: Maybe I have proved it in 1993~1995.
|
c**y
发帖数: 391 | 44
O(N^P) 和 O(N) 都是 P 问题?
【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
|
c**y
发帖数: 391 | 45
错了，错的很离谱
【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
|
b***u
发帖数: 12010 | 46 围观民科。。。
【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
|
b***u
发帖数: 12010 | 47 我真的很想转joke...
【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
|
w***g
发帖数: 5958 | 48 mytbbs经常在这里装二愣子娱乐大家，您老千万别当真...
【在 b***u 的大作中提到】
: 我真的很想转joke...
|
M**u
发帖数: 10158 | 49 mytbbs绝对是高人，深藏不露的。。。肯定不是民科
算复
【在 b***u 的大作中提到】
: 围观民科。。。
|
l******e
发帖数: 470 | 50 ding
【在 w***g 的大作中提到】
: mytbbs经常在这里装二愣子娱乐大家，您老千万别当真...
|
|
|
i*********8
发帖数: 3229 | 51 cs 版有两个著名的版宠
一个是mytbbs，一个是netghost
【在 w***g 的大作中提到】
: mytbbs经常在这里装二愣子娱乐大家，您老千万别当真...
|
d******e
发帖数: 7844 | 52 re,ahaha
【在 i*********8 的大作中提到】
: cs 版有两个著名的版宠
: 一个是mytbbs，一个是netghost
|
b***u
发帖数: 12010 | 53 哦这样啊。。
【在 w***g 的大作中提到】
: mytbbs经常在这里装二愣子娱乐大家，您老千万别当真...
|
