logo
Redian新闻
>未名空间
>CS - 计算机科学
>
P != NP 被证出来了，同学们
avatar
P != NP 被证出来了，同学们# CS - 计算机科学
z*z
1 楼
2001年的盛夏，一时冲动跟着朋友去了贵州支教，山很清，水很秀，老乡们很纯朴，孩
子们也很天真，可是那时的我却只看到生活很苦，只知道埋怨要看不到申奥结果的现场
直播了，从第一天开始就掰着手指算日子。每天硬着头皮备课上课，挤着笑容回答孩子
们的问题，却在心里嘲笑他们连这么简单的东西都不会。盼星星盼月亮的盼来了最后一
天，站在台上和孩子们告别，结果自己刚说了个“我”字就开始掉眼泪，后来干脆站在
那里哭了个稀里哗啦，哎，年轻的自己还真是肤浅，可以回城就激动成那样………
2003年的初夏，整个北京城都笼罩在非典的恐慌中，单位早早放了暑假，我们这些向来
被当作万金油使的外地单身职工也一如既往地被要求留下来看家护院。那时的单身宿舍
是个小四合院，每天早上，大家都会敞着门相互吆喝相互奚落，磨磨蹭蹭的起床，当值
男职工负责买早点，当值女职工负责扫院子，吃饱喝足便开始下棋打牌侃大山一直到食
堂开午饭，吃过午饭，午睡到四五点，跑到隔壁公园跑步打球遛弯，回家路上顺便买点
毛豆花生小龙虾，晚上在院子里摆夜宵摊子，一边乘凉一边爬屋顶数星星。每天都乐此
不疲地重复着同样的程序，大笑，大哭，大闹。后来，小院拆了，我
avatar
t*l
2 楼
HP lab的一个研究员。
avatar
g*g
3 楼
Wow, really? That's really a breakthrough if true.

【在 t*********l 的大作中提到】
: HP lab的一个研究员。
avatar
K*n
4 楼
原来除了性骚扰HP还有这么大一新闻。
avatar
v*e
6 楼
真depressing..

【在 t*********l 的大作中提到】
: HP lab的一个研究员。
avatar
w*s
7 楼
不知道几个人看得懂啊，横跨若干大领域。
这人不像民科，所以还真说不定提出了一些新颖的想法。
avatar
m*s
9 楼
搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。

【在 t*********l 的大作中提到】
: HP lab的一个研究员。
avatar
a*9
10 楼

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ P \subseteq NP

【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
avatar
w*s
11 楼
不管结果怎么样，能证出来，应该还是有新发现的。
一般来说，都要牵动多个领域，发展一些新的工具。
纯科学研究嘛，就包括满足好奇心。不到黄河心不死。

【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
avatar
a*9
12 楼
再等等,
现在还只是他自己claim证出来了
要看其他人会不会挑出来错

【在 t*********l 的大作中提到】
: HP lab的一个研究员。
avatar
m*s
13 楼
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
avatar
t*a
14 楼
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)。
avatar
l*8
17 楼
你的理解错误。
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)。
avatar
l*8
19 楼
用一个不太严格的比方，RSA算法的基础是分解两个素数需要的时间是NP问题，但不是P
问题。对知道密钥的来说只要多项式时间就能分解，对不知道密钥的来说是个NP问题，
如果想多项式时间算出，就只能蒙。RSA的基础就是假设不存在一个确定性的算法在多
项式时间内可以分解素数的乘积。
如果P=NP的话，那么所有NP问题就能转化为P问题，公开密钥系统就马上崩溃了。
avatar
d*f
22 楼
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.
avatar
m*s
23 楼
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之间的数。如果你蒙对了，那么一步就算出来了。所以确定性算法
: 通常比非确定性算法更费时间。但要从理论上证明则是非常难得。
avatar
w*o
24 楼
1+1 =2 不是需要证明的么

【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
avatar
l*u
25 楼
我怎么觉得，你说的没一个对的？

【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
avatar
w*n
26 楼
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也要证。
:
: ..
avatar
l*8
27 楼
No. 2^N这样的复杂度通常称为EXP (exponential),或者叫指数复杂度。
P<=NP<=EXP.第一个可以去掉等号如果这个证明是正确的。但NP未必等于EXP.
PNP事实上这个一点都不明显。比如 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也要证。
:
: ..
avatar
m*u
28 楼
你解释的太复杂了。

【在 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问题。
avatar
s*g
29 楼
你根本没懂P和NP的定义
建议你先去wiki科普一下
推荐你看一本日本侦探小说叫嫌疑犯x的献身，里面用破案给P和NP打了一个比方，很有趣

【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
avatar
a*9
30 楼
你这对P,NP的理解根本就是错的,
我发现不少人(甚至包括不少cs科班出身的)望文生义的以为
P就是polynormial
NP就是non-polynormial
要我说 这名字确实也起的不好

面至
。如
7,
可以
算法

【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
avatar
Y*y
31 楼

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
应该说是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问题。
avatar
l*8
32 楼
是的，所以PSPACE=NPSPACE.不过严格的证明也不是很简单

【在 Y*****y 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 应该说是deterministic和nondeterministic花的空间几乎是一样吧，因为前者可以在
: 不太多额外空间的条件下simulate后
: 者。
avatar
l*8
33 楼
是的。我再试着重新解释一遍：
P和NP涉及到两种不同的算法,确定性的和不确定性的。前者就是通常意义上的算法，算
完第一步怎么算下一步都是确定的，计算机程序基本都是确定性的算法。非确定性算法
则带有蒙的性质，就像走迷宫，走到某一步你可以有左，右，向前三种选择，下一步可
能又有三种选择。没人告诉你那条路可以出去。但肯定有一条路是通的。
P问题就是说有一个确定性的算法，用多项式时间可以算出答案。
NP问题就是说有一个类似迷宫算法，肯定有一条路（当然也可能有多条路)是通的，而
且如果你碰巧走了最短的路，那只要多项式时间就能走完。
所以P问题一定也是NP问题，因为确定性算法是非确定性算法的特例。任何一个非确定
性算法也可以用确定性算法来模拟：只要穷举每一条可能的路线就行了。但这种穷举方
法就不是多项式时间可以算完的了。

【在 m*****u 的大作中提到】
: 你解释的太复杂了。
avatar
r*l
34 楼
确实，无数人认为NP是Non Polynomial的缩写，肯定是上课时睡觉了。。。

【在 a****9 的大作中提到】
: 你这对P,NP的理解根本就是错的,
: 我发现不少人(甚至包括不少cs科班出身的)望文生义的以为
: P就是polynormial
: NP就是non-polynormial
: 要我说 这名字确实也起的不好
:
: 面至
: 。如
: 7,
: 可以
avatar
Y*y
35 楼
说反了？
不过这样说也不完全对。因为到目前为止还没人（这篇paper的结果暂时未定）证明一
定没有很efficient的search的办法…
search也不一定非要enumerate吧：）有点抓字眼了，不好意思。

search
avatar
l*8
36 楼
你的直觉很对。如果证明P=NP，只要能找到一个超级efficient的搜索算法就行了。问
题是这样的算法一般认为不存在。

【在 Y*****y 的大作中提到】
: 说反了？
: 不过这样说也不完全对。因为到目前为止还没人（这篇paper的结果暂时未定）证明一
: 定没有很efficient的search的办法…
: search也不一定非要enumerate吧：）有点抓字眼了，不好意思。
:
: search
avatar
Y*y
37 楼
呵呵，我的直觉是P!=NP。不然整个人类社会就彻底改变了，至少那些crypto的system
基本都废了。 不过我不是专门搞
complexity的，所以只有旁观的份。

【在 l*****8 的大作中提到】
: 你的直觉很对。如果证明P=NP，只要能找到一个超级efficient的搜索算法就行了。问
: 题是这样的算法一般认为不存在。
avatar
p*g
38 楼
不过我一直搞不懂，既然叫 non-deterministic polynomial, 那总有什么东东是
polynomial 的吧?
avatar
s*b
39 楼
如果俺没有记错的话，假设一个NP问题可能解的集合是S，那么
您老同时调用|S|台图灵机，每台机器验证条可能解。这个算法肯
定是多项式的，问题是您老不知道哪台机器算出正确结果，所以它
是non-deterministic的。

【在 p*********g 的大作中提到】
: 不过我一直搞不懂，既然叫 non-deterministic polynomial, 那总有什么东东是
: polynomial 的吧?
avatar
b*e
40 楼
刚上网就发现这么令人震惊的消息。。。。
avatar
d*e
42 楼
外行容易犯的错误.

【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
avatar
D*h
43 楼
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? "
avatar
c*y
45 楼

O(N^P) 和 O(N) 都是 P 问题?

【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
avatar
c*y
46 楼

错了，错的很离谱

【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
avatar
b*u
47 楼
围观民科。。。

【在 m****s 的大作中提到】
: 搞不懂搞计算机的在做什么，要证P==NP还有用，证P!=NP，那不是直观的事实？计算复
: 杂度为NP的怎么也不会成为P的，O(N^P)永远都不能为O(N)。
avatar
b*u
48 楼
我真的很想转joke...

【在 m****s 的大作中提到】
: P问题是O(N)的，NP是>O(N)的，比如2^N，这没错吧？
: 数学要这样的话，是不是1!=2也要证。
:
: ..
avatar
w*g
49 楼
mytbbs经常在这里装二愣子娱乐大家，您老千万别当真...

【在 b***u 的大作中提到】
: 我真的很想转joke...
avatar
M*u
50 楼
mytbbs绝对是高人，深藏不露的。。。肯定不是民科

算复

【在 b***u 的大作中提到】
: 围观民科。。。
avatar
l*e
51 楼
ding

【在 w***g 的大作中提到】
: mytbbs经常在这里装二愣子娱乐大家，您老千万别当真...
avatar
i*8
52 楼
cs 版有两个著名的版宠
一个是mytbbs，一个是netghost

【在 w***g 的大作中提到】
: mytbbs经常在这里装二愣子娱乐大家，您老千万别当真...
avatar
d*e
53 楼
re,ahaha

【在 i*********8 的大作中提到】
: cs 版有两个著名的版宠
: 一个是mytbbs，一个是netghost
avatar
b*u
54 楼
哦这样啊。。

【在 w***g 的大作中提到】
: mytbbs经常在这里装二愣子娱乐大家，您老千万别当真...
相关阅读
问几个网络的会议现在ECE哪些方向是火坑？ (转载)ITNG 這會 怎麼樣job openings in bay areaUpdated: Summer Research Internship请教CS方向的问题--对coding丝毫不感兴趣请高手帮我解决笔记本电脑问题Entry level Job Opportunity from Elite从machine learning转economics可在哪些刊物发论文？关于牛顿法求函数的最值的复杂度有没有人说说image processing之类的还有什么比较新的热门点hotmail打印时出现一行就是一段现象怎么解决?大家帮看看这个问题可以用啥 model 解决 ~ 谢谢。［请置顶］researcher/engineer/consultant positions at eBay Researchonline ad 方面的论文怎样判断两个时间序列的相似度有谁熟悉 国内复旦大学臧斌宇老师的GROUP？SJSU MS CS就业前景如何？为啥IE8性能还赶不上人家开源的Firefox!?!?真的还是假的？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。