科学网—accsys的博文

P vs. NP 问题的总结

姜咏江 2019-12-27 05:33

姜咏江 accsys@126.com 2016 年我在科学网上发表了《多项式时间复杂度和指数时间复杂度相差多少？》的博文，设计了仿量子计算机之后，才敢肯定此那里结论的正确性。现将原文再次贴到本文的后面，作为 4 年之后的进一步肯定。学界早已认可， ...

个人分类: P/NP问题|2899 次阅读|没有评论

如果密码都能被瞬间破解将会怎样？

热度 1 姜咏江 2018-2-7 17:10

研究出了SAT同时处理器SPU,我有些害怕了。都说任何的密文都可以变换成合取范式CNF，而SPU处理器可以在分秒之间求出SAT的全部解，这意味从此没有安全的密码了？我不是搞密码的专家，是否果真的如此，我不敢乱讲。但，无论如何，此生，能够创造出一种新的处理器，我心满足。

个人分类: P/NP问题|3397 次阅读|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问题|3056 次阅读|1 个评论

计算机科学P/NP问题并行计算处理器研制成功!

热度 1 姜咏江 2018-1-20 12:38

纯离散数据并行处理运算器计算机征询合作者姜咏江现在的计算机处理器，本质上是一种顺序处理方式的产物。这种计算机处理连续数据的问题非常有效，但处理象哈密顿回路、超大规模集成电路可靠性、密码破译、人工智能、基因准确计算等一系列纯离散数据类型的问题时，计算的时间复杂度都是指数型的 ...

个人分类: P/NP问题|4303 次阅读|1 个评论热度 1

通俗解释P与NP这个世界难题

姜咏江 2017-11-8 07:11

通俗解释 P 与 NP 这个世界难题姜咏江与人工智能关系重大的 P 与 NP 问题，是美国克雷数学所千禧年以百万美元大奖悬赏的七大难题之一。通俗地讲，就是“最坏在指数时间可以猜测验证答案的问题，是否可以在多项式时间求出一个正确答案”。前类问题称为 NP ，后类 ...

个人分类: P/NP问题|7547 次阅读|没有评论

NPC=P

姜咏江 2017-10-22 12:22

NPC=P 姜咏江我说过， “搞创新科学研究就如同坐过山车。”在设计 3-SAT 问题求满足解程序的过程中，又让我坐了一次过山车。在用子句消去法求出联想的满足解，最后遇到了全是孤立变量的情况，而且孤立变量形成的 3-SAT 也可以无解！这是我先前没有深入思考的。经过一个多月的深入研究，变换思路 ...

个人分类: P/NP问题|2508 次阅读|没有评论

P与NP问题为什么会成为百万美元大奖的世界难题？

姜咏江 2017-8-22 07:22

P 与 NP 问题为什么会成为百万美元大奖的世界难题？姜咏江 P 与 NP 问题是美国克雷数学所悬赏百万美元大奖的七大世界难题之一。简单地说，用计算机在多项式时间内求出解的一类问题，称为 P 类问题；而在多项式时间可以验证是否是解的问题，称为 NP 类问题。回答 P 与 NP 是同一类问题吗？这就是 P ...

个人分类: P/NP问题|3727 次阅读|没有评论

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问题|3711 次阅读|没有评论

廉颇老矣尚能编程否？

热度 1 姜咏江 2017-8-11 05:22

廉颇老矣尚能编程否？七十二岁，还能够自己编写计算机程序否？可，只要科学安排自己的体力。为了向学界证明我的子句消去法能够完备地求出 3-SAT 问题满足解，我不得不拼了老命，自己编写计算机程序。因为这种计算机科学的最大问题，只有通过计算机程序的验证，才能够有效地说明我的发明创造的正确性。我先 ...

个人分类: P/NP问题|4260 次阅读|3 个评论热度 1

求解世界难题如同坐过山车刺激富有吸引力

姜咏江 2017-6-21 21:27

求解世界难题如同坐过山车刺激富有吸引力姜咏江一晃，研究 P/NP 世界难题已经过去三年多了。在求解 SAT 问题多项式时间算法的研究中，真感到了玩“过山车”般的惊险刺激，然而却是那样充满了吸引力。当我将 3-SAT 一般性求解程序设计完成之后，我才踏实地感觉到， Boolean Satisfiability Problem ...

个人分类: P/NP问题|3547 次阅读|没有评论

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

accsys

关闭安全验证