f*****s
发帖数: 95 | 1 Vinay Deolalikar from HP Labs claimed to have proved NP =\= P! and
it seems to have survived two days of scrutiny.
http://www.hpl.hp.com/personal/Vinay_Deolalikar/ |
l********e
发帖数: 3632 | |
v********e
发帖数: 1058 | 3 说是在工作之余证的。。
【在 l********e 的大作中提到】
: HP养这样的人有什么用处？
|
m*********a
发帖数: 2000 | 4 hope it is correct, hoho
【在 f*****s 的大作中提到】
: Vinay Deolalikar from HP Labs claimed to have proved NP =\= P! and
: it seems to have survived two days of scrutiny.
: http://www.hpl.hp.com/personal/Vinay_Deolalikar/
|
p**********0
发帖数: 101 | 5 这个问题会不会象《连续统假设》问题一样？其数学公理化定义不清？如是，该证明多
半站不住。 |
w****e
发帖数: 2210 | |
N***m
发帖数: 4460 | 7 N=\=1
【在 w****e 的大作中提到】
: 他们在证明什么？俺一窍不通。
|
m**k
发帖数: 1008 | 8 P≠NP，一个简洁的论文标题，或许预示着七大世界数学难题之一的P问题（多项式算法
）对NP问题（非多项式算法）终于有了答案。据英国《新科学家》杂志网站8月11日（
北京时间）报道，美国惠普实验室的数学家维奈·迪奥拉里卡已经于6日提交了关于论
证该问题的论文草稿，如果此答案被证实无误，那么他将获得由美国克雷数学研究所提
供的100万美元奖金。
P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领
域的最大难题，关系到计算机完成一项任务的速度到底有多快。有些问题计算起来很容
易，利用多项式算法很快能解决，比如求若干个数的乘积，这类问题被称作P问题；另
一类问题计算过程比较繁琐，但验证答案却很容易，比如把整数44427进行因数分解，
求解过程可能会很费时，但如果告诉你答案是177×251，简单计算即可验证答案是对的
，这类问题就被归为NP问题。
因此，如果P=NP，那么每个答案很容易得到验证的问题也同样可以轻松求解。这将对计
算机安全构成巨大威胁，目前加密系统的破解就相当于要将一个整数分解为几个因数的
乘积，正是其求解过程的繁琐，才能杜绝黑客的入侵。
而现在，迪奥拉 |
g****t
发帖数: 31659 | 9 专家提了问题，在等作者回答。
关于这个文章,目前已经有个wiki。
【在 m**k 的大作中提到】
: P≠NP，一个简洁的论文标题，或许预示着七大世界数学难题之一的P问题（多项式算法
: ）对NP问题（非多项式算法）终于有了答案。据英国《新科学家》杂志网站8月11日（
: 北京时间）报道，美国惠普实验室的数学家维奈·迪奥拉里卡已经于6日提交了关于论
: 证该问题的论文草稿，如果此答案被证实无误，那么他将获得由美国克雷数学研究所提
: 供的100万美元奖金。
: P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领
: 域的最大难题，关系到计算机完成一项任务的速度到底有多快。有些问题计算起来很容
: 易，利用多项式算法很快能解决，比如求若干个数的乘积，这类问题被称作P问题；另
: 一类问题计算过程比较繁琐，但验证答案却很容易，比如把整数44427进行因数分解，
: 求解过程可能会很费时，但如果告诉你答案是177×251，简单计算即可验证答案是对的
|
j******w
发帖数: 690 | 10 probably a joke
【在 f*****s 的大作中提到】
: Vinay Deolalikar from HP Labs claimed to have proved NP =\= P! and
: it seems to have survived two days of scrutiny.
: http://www.hpl.hp.com/personal/Vinay_Deolalikar/
|
a********1
发帖数: 73 | 11 基本可以肯定证明不对了,据说他证明的其实是个更简单的statement,甚至有个半页的
简单证明.
"迪奥拉里卡的论文草稿已经得到了复杂性理论家的认可"--这个也是作者自己说的.8月
12号他在网站上贴出证明初稿,然后说他已经把初稿寄给一些专家(10号左右?),说是
confirmations have been arriving already之类的,比较误导.他的初稿就102页,这么
几天也没人能说证明是对的. |
v********e
发帖数: 1058 | 12 哪个复杂理论专家“认可”了……现在的记者真没治了
【在 m**k 的大作中提到】
: P≠NP，一个简洁的论文标题，或许预示着七大世界数学难题之一的P问题（多项式算法
: ）对NP问题（非多项式算法）终于有了答案。据英国《新科学家》杂志网站8月11日（
: 北京时间）报道，美国惠普实验室的数学家维奈·迪奥拉里卡已经于6日提交了关于论
: 证该问题的论文草稿，如果此答案被证实无误，那么他将获得由美国克雷数学研究所提
: 供的100万美元奖金。
: P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领
: 域的最大难题，关系到计算机完成一项任务的速度到底有多快。有些问题计算起来很容
: 易，利用多项式算法很快能解决，比如求若干个数的乘积，这类问题被称作P问题；另
: 一类问题计算过程比较繁琐，但验证答案却很容易，比如把整数44427进行因数分解，
: 求解过程可能会很费时，但如果告诉你答案是177×251，简单计算即可验证答案是对的
|
m****m
发帖数: 2211 | 13 To me, the proof is so complicated it is NP-complete to find an error. So by
recursion the proof is polynomially correct.
【在 a********1 的大作中提到】
: 基本可以肯定证明不对了,据说他证明的其实是个更简单的statement,甚至有个半页的
: 简单证明.
: "迪奥拉里卡的论文草稿已经得到了复杂性理论家的认可"--这个也是作者自己说的.8月
: 12号他在网站上贴出证明初稿,然后说他已经把初稿寄给一些专家(10号左右?),说是
: confirmations have been arriving already之类的,比较误导.他的初稿就102页,这么
: 几天也没人能说证明是对的.
|
