SatZ( http://blog.sciencenet.cn/blog-2322490-991076.html )的作者提供了一个k-SAT实例生成器程序:gencnf+.c,为对SAT问题感兴趣的网友提供一个比较自己和他人工作的工具。 1. To compile under Linux or Unix : gcc gencnf+.c -O3 -o gencnf+ 2. To generate a set of (s2-s1+1) different k-sat instances of n ...
Alan Cobham(1927-2011)在1965年的文章“The Intrinsic Computational Difficulty of Functions”中最早提出“多项式时间复杂度问题类P”,Cook在其1971年的著名论文“The complexity of theorem proving procedures”中引用,被认为是计算复杂性理论的重要论文之一,由此有所谓的“Cobham论题”( https://en.wikipedi ...