求真分享 http://blog.sciencenet.cn/u/zlyang 求真务实

博文

感谢“中科院科学智慧火花”:某些NPI 可能是处在相变边界的NPC

已有 5292 次阅读 2015-12-24 12:11 |系统分类:科研笔记|关键词:某些,,NPI,,可能,,处在,,相变,,边界,,NPC,,CH,,P,vs,,NP| 相变, 可能, NPI, 某些, 处在

感谢“中科院科学智慧火花”:

某些 NPI 可能是处在相变边界NPC

                     

      从王小平老师的博客里看到2015年 Knuth Prize 得主,芝加哥大学的数学和计算机科学教授 László Babai 宣布他想出了一个新的解决“图同构”问题的算法——这个问题在计算机科学中算得上是最诱人的奥秘。


一时兴起,偶有心得,蒙“中科院科学智慧火花”审查,给予贴出:


感谢并祝福“中科院科学智慧火花”!

核心:

    某些NPC,随着数量关系的增加,存在从P到NPC的相变。猜想:某些NPI可能是处在相变边界的NPC。

    “约翰逊图 Johnson graphs” 会不会是NPC的?


以上想法,不是深思熟虑的结果。只是一时的心得或猜想。

相关链接:

[1] 王小平,2015-12-18,[转载]著名数学家宣布解决算法难题,或打破30年僵局

http://blog.sciencenet.cn/blog-1225851-944276.html

[2] Erica Klarreich, December 14, 2015, COMPUTER SCIENCE, Landmark Algorithm Breaks 30-Year Impasse, Computer scientists are abuzz over a fast new algorithm for solving one of the central problems in the field.

https://www.quantamagazine.org/20151214-graph-isomorphism-algorithm/

[3] László Babai, Submitted on 11 Dec 2015, Graph Isomorphism in Quasipolynomial Time

http://arxiv.org/abs/1512.03547v1

[4] László Babai's Home Page - Departments of Computer Science and Mathematics, University of Chicago

http://people.cs.uchicago.edu/~laci/

[5] Complexity theory. G. RozenbergA. Salomaa (originator), Encyclopedia of Mathematics.

http://www.encyclopediaofmath.org/index.php?title=Complexity_theory&oldid=14425

[6] NP. Hubertus Th. JongenKlaus Meer (originator), Encyclopedia of Mathematics.

http://www.encyclopediaofmath.org/index.php?title=NP&oldid=15503

[7] Algorithm, computational complexity of an. N.V. Petri (originator), Encyclopedia of Mathematics.

http://www.encyclopediaofmath.org/index.php?title=Algorithm,_computational_complexity_of_an&oldid=17564

[8] 2015-05-22,The kernel of "P vs NP Problem": Axiom of power set!

http://blog.sciencenet.cn/blog-107667-892400.html

[9] 正式的介绍材料之一,2012-03-23,[请教] P对NP:请郝克刚教授等专家指教(一)

http://blog.sciencenet.cn/blog-107667-550859.html

[10] 科学智慧火花,2011-08-30,P对NP”难题研究的形转换新思路

http://idea.cas.cn/viewdoc.action?docid=1275#d1 

                             

感谢您指正以上任何错误!



http://blog.sciencenet.cn/blog-107667-945568.html

上一篇:[请教] 孙小淳老师《 苏联专家谈中国的“科学文化”》的真实性
下一篇:圣诞节是假的:耶稣不是上帝的儿子

32 朱晓刚 檀成龙 罗教明 马青平 王小平 李竞 李轻舟 张珑 李颖业 李俊 王春艳 王毅翔 蔡小宁 侯成亚 陈楷翰 蔡宁 谢力 徐晓 文克玲 马志超 徐令予 谢平 籍利平 徐传胜 刘炜 蒋永华 柳渝 dulizhi95 gaoshannankai seaocean icgwang biofans

该博文允许注册用户评论 请点击登录 评论 (39 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-5-24 16:58

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部