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

某些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://blog.sciencenet.cn/blog-107667-945568.html

全部精选博文导读

GMT+8, 2020-6-1 07:39