The entropy of SAT problem
Feng Pan · arXiv (Cornell University) · 2015
In this paper with two equivalent representations of the information contained by a SAT formula, the reason why string generated by succinct SAT formula can be greatly compressed is firstly presented based on Kolmogorov complexity theory. Then what strings can be greatly compressed were classified and discussed. The equivalence of computation and information was clearly stated in succession. In the last the entropy of SAT problem was computed based on universal probability. The experiment results showed the information gained by solving SAT problem was quite likely exponentially increased.