科学网

 找回密码
  注册
P vs. NP 问题的总结
姜咏江 2019-12-27 05:33
姜咏江 accsys@126.com 2016 年我在科学网上发表了《多项式时间复杂度和指数时间复杂度相差多少?》的博文,设计了仿量子计算机之后,才敢肯定此那里结论的正确性。现将原文再次贴到本文的后面,作为 4 年之后的进一步肯定。 学界早已认可, ...
个人分类: P/NP问题|2438 次阅读|没有评论
如果密码都能被瞬间破解将会怎样?
热度 1 姜咏江 2018-2-7 17:10
研究出了SAT同时处理器SPU,我有些害怕了。都说任何的密文都可以变换成合取范式CNF,而SPU处理器可以在分秒之间求出SAT的全部解,这意味从此没有安全的密码了?我不是搞密码的专家,是否果真的如此,我不敢乱讲。但, 无论如何,此生,能够创造出一种新的处理器,我心满足。
个人分类: P/NP问题|3118 次阅读|4 个评论 热度 1
P与NP问题的认知盲点
姜咏江 2018-1-23 10:49
P versus NP 问题的认知盲点 姜咏江 The P versusNP problem is a major unsolved problem incomputer science . It asks whether every problem whose solution can bequickly verified (technically, verified in polynomialtime ) can also be solved quickly (again, in polynomial time). &n ...
个人分类: P/NP问题|2776 次阅读|1 个评论
计算机科学P/NP问题并行计算处理器研制成功!
热度 1 姜咏江 2018-1-20 12:38
纯离散数据并行处理运算器计算机征询合作者 姜咏江 现在的计算机处理器,本质上是一种顺序处理方式的产物。这种计算机处理连续数据的问题非常有效,但处理象哈密顿回路、超大规模集成电路可靠性、密码破译、人工智能、基因准确计算等一系列纯离散数据类型的问题时,计算的时间复杂度都是指数型的 ...
个人分类: P/NP问题|4004 次阅读|1 个评论 热度 1
通俗解释P与NP这个世界难题
姜咏江 2017-11-8 07:11
通俗解释 P 与 NP 这个世界难题 姜咏江 与人工智能关系重大的 P 与 NP 问题,是美国克雷数学所千禧年以百万美元大奖悬赏的七大难题之一。通俗地讲,就是“最坏在指数时间可以猜测验证答案的问题,是否可以在多项式时间求出一个正确答案”。前类问题称为 NP ,后类 ...
个人分类: P/NP问题|7017 次阅读|没有评论
NPC=P
姜咏江 2017-10-22 12:22
NPC=P 姜咏江 我说过, “搞创新科学研究就如同坐过山车。”在设计 3-SAT 问题求满足解程序的过程中,又让我坐了一次过山车。在用子句消去法求出联想的满足解,最后遇到了全是孤立变量的情况,而且孤立变量形成的 3-SAT 也可以无解!这是我先前没有深入思考的。 经过一个多月的深入研究,变换思路 ...
个人分类: P/NP问题|2242 次阅读|没有评论
P与NP问题为什么会成为百万美元大奖的世界难题?
姜咏江 2017-8-22 07:22
P 与 NP 问题为什么会成为百万美元大奖的世界难题? 姜咏江 P 与 NP 问题是美国克雷数学所悬赏百万美元大奖的七大世界难题之一。简单地说,用计算机在多项式时间内求出解的一类问题,称为 P 类问题;而在多项式时间可以验证是否是解的问题,称为 NP 类问题。回答 P 与 NP 是同一类问题吗?这就是 P ...
个人分类: P/NP问题|3443 次阅读|没有评论
Look at This paper,Why Do TOCS not Touch It?
姜咏江 2017-8-11 19:01
Mathematical Theory of Clause Elimination Algorithm for SAT_acm00.pdf
个人分类: P/NP问题|3376 次阅读|没有评论
廉颇老矣尚能编程否?
热度 1 姜咏江 2017-8-11 05:22
廉颇老矣尚能编程否? 七十二岁,还能够自己编写计算机程序否?可,只要科学安排自己的体力。 为了向学界证明我的子句消去法能够完备地求出 3-SAT 问题满足解,我不得不拼了老命,自己编写计算机程序。因为这种计算机科学的最大问题,只有通过计算机程序的验证,才能够有效地说明我的发明创造的正确性。 我先 ...
个人分类: P/NP问题|3946 次阅读|3 个评论 热度 1
求解世界难题如同坐过山车刺激富有吸引力
姜咏江 2017-6-21 21:27
求解世界难题如同坐过山车刺激富有吸引力 姜咏江 一晃,研究 P/NP 世界难题已经过去三年多了。在求解 SAT 问题多项式时间算法的研究中,真感到了玩“过山车”般的惊险刺激,然而却是那样充满了吸引力。 当我将 3-SAT 一般性求解程序设计完成之后,我才踏实地感觉到, Boolean Satisfiability Problem ...
个人分类: P/NP问题|3282 次阅读|没有评论

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-28 22:13

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部