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

某些 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 

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