Probabilistic phenomena in random combinatorial problems

[摘要] This is an experimental investigation of three combinatorial problems. I examined the average-case complexity of random 3-SAT and of 3-Colorability of random graphs, and the satisfiability of random 1-3-HornSAT. All these problems, not only are interesting for their own sake, but also are of great practical importance since many other problems in computer science, engineering and other fields can be reduced to these. We systematically explored a large part of the problems;; space, varying the size and the constrainedness of the instances, as well as the tools we used to solve them. We observed new phase transitions from polynomial to exponential complexity for random 3-SAT. A similar picture emerged for 3-Colorability. These experimental observations are important for understanding the inherent computational complexity of the problems. In the case of random 1-3-HornSAT, our findings suggest that there is a threshold at which the satisfiability changes from 1 to 0.

[发布机构] Rice University