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 ...
在图灵1936年论文第二章,图灵用circle-free来定义“可计算数(Computable sequences and numbers)”,这个定义实际上是由二部份构成的,首先由circle-free来定义“可计算序列”,进一步由“可计算序列”定义“可计算数”。 按照图灵的定义: A sequence is said to be computable if it can be computed by a circle-f ...
Alan Cobham(1927-2011)在1965年的文章“The Intrinsic Computational Difficulty of Functions”中最早提出“多项式时间复杂度问题类P”,Cook在其1971年的著名论文“The complexity of theorem proving procedures”中引用,被认为是计算复杂性理论的重要论文之一,由此有所谓的“Cobham论题”( https://en.wikipedi ...