24小时热门版块排行榜    

查看: 1661  |  回复: 25

nkyle

银虫 (小有名气)

【答案】应助回帖

引用回帖:
11楼: Originally posted by hhxzj at 2013-09-23 09:33:48
NPC问题是不是指数级复杂度还不确定,因为到现在没有人能够证明P!=NP,只是很多人相信P!=NP。如果要放弃对精确算法的研究,前提是有人能够证明P!=NP!如果大家都去研究近似的P算法,P vs. NP这个问题何时能解?总不 ...

我是做密码的,密码学的基础就是假设P!=NP。如果推翻这个假设,这个世界将无密可保,这是无法想象的,因此绝大多数学者相信P!=NP。
如果有人能证明P!=NP或P==NP,没有任何悬念,必然拿图灵奖。岂今有几个Open problem可以拿图灵奖(计算机界中的诺贝尔),证明P!=NP貌似是其中一个。
换句话说,P!=NP是必然的。只是现在还没有人能够证明而已。
21楼2013-09-23 20:24:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

人民海军

木虫 (职业作家)

引用回帖:
17楼: Originally posted by hhxzj at 2013-09-23 11:58:37
遍历暴力(或减枝)解决也并不是适用所有的情况的。
我设计的算法思路是:
把布尔函数化简(也是NP问题)算法(Q_M算法)与DB领域的一个经典算法结合起来,在一个新的定义的基础上,通过数学反证法证明(这是我觉 ...

你误会我的意思了,我的意思是与已有的算法比较,你的算法有什么优点?时间复杂度的改进还是空间复杂度的改进?从应用的角度,好的工作不但要友创新,还万有改进,也就是说要比原来得算法好。如果以上优点都有的话,我认为绝对可以投top magazine了,不过中不中,文章的写作水平也很重要

[ 发自小木虫客户端 ]
Letbygonesbebygones.
22楼2013-09-24 06:46:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hhxzj

新虫 (小有名气)

引用回帖:
22楼: Originally posted by 人民海军 at 2013-09-24 06:46:13
你误会我的意思了,我的意思是与已有的算法比较,你的算法有什么优点?时间复杂度的改进还是空间复杂度的改进?从应用的角度,好的工作不但要友创新,还万有改进,也就是说要比原来得算法好。如果以上优点都有的话 ...

我的算法是为初步解决一个问题而设计的,是原创性的,我所知道的是没有已有的算法(JACM的paper提出来的问题,至少我没看见谁设计了相关算法,当然可能也有),不存在比较!
23楼2013-09-24 08:42:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hhxzj

新虫 (小有名气)

引用回帖:
21楼: Originally posted by nkyle at 2013-09-23 20:24:02
我是做密码的,密码学的基础就是假设P!=NP。如果推翻这个假设,这个世界将无密可保,这是无法想象的,因此绝大多数学者相信P!=NP。
如果有人能证明P!=NP或P==NP,没有任何悬念,必然拿图灵奖。岂今有几个Open pro ...

NPC概念的提出者,1982年图灵奖得主Stephen Cook也认为P!=NP。他也强调,如果P=NP,那么密码学将崩溃。Complexity theory至少已经产生3个图灵奖了(初步统计),未来肯定还会有的。
你是做密码的,Stephen Cook认为证明密码系统的安全性比证明P!=NP更难。Stephen Cook也认为就算P=NP,不一定就能对每个NPC问题都能找到一个高效的算法。打个比方,给你一道数学超级难题,而且告诉你有答案,但是,关键的是,可能给你一辈子也解不出来。另外,虽然我不是做密码的,但是我相信中国的一句古话“没有不透风的墙”,密码学所面临的威胁我想绝对不仅仅是P=NP?!。所以,我觉得,没必要把密码学与P=NP?!联系的太紧密,它只是告诉我们某些问题是很难解的,甚至是不可解的。
个人愚见!
24楼2013-09-24 09:03:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

nkyle

银虫 (小有名气)

引用回帖:
24楼: Originally posted by hhxzj at 2013-09-24 09:03:15
NPC概念的提出者,1982年图灵奖得主Stephen Cook也认为P!=NP。他也强调,如果P=NP,那么密码学将崩溃。Complexity theory至少已经产生3个图灵奖了(初步统计),未来肯定还会有的。
你是做密码的,Stephen Cook认 ...

什么是可解?难解?什么是很难解?什么是不可解?
在没有一个统一概念的情况下,讨论已经没有意义。
举个例子,在普通小型数据库中 顺序搜索的时间复杂度是O(n),是可解的。但是在大数据情形下,复杂度为O(n)的算法在现行条件下却是不可解的。
25楼2013-09-24 20:45:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

cxlzxc123

新虫 (初入文坛)

专业不同,但是技巧差不多吧,按自己的论文水平,和杂志的偏重方向选择期刊!
26楼2013-09-25 21:10:37
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 hhxzj 的主题更新
信息提示
请填处理意见