On the solution-space geometry of random constraint satisfaction problems. (English) Zbl 1217.68156
Summary: For various random constraint satisfaction problems there is a significant gap between the largest constraint density for which solutions exist and the largest density for which any polynomial time algorithm is known to find solutions. Examples of this phenomenon include random \(k\)-SAT, random graph coloring, and a number of other random constraint satisfaction problems. To understand this gap, we study the structure of the solution space of random \(k\)-SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number of connected components and give quantitative bounds for the diameter, volume, and number.
MSC:
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
Keywords:
random formulas; satisfiability; \(k\)-SAT; statistical mechanics; computational complexityReferences:
| [1] | Achlioptas, In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS’08) pp 793– (2008) |
| [2] | Achlioptas, In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’02) pp 126– (2002) |
| [3] | Achlioptas, Rigorous location of phase transitions in hard optimization problems, Nature 435 pp 759– (2005) · doi:10.1038/nature03602 |
| [4] | Achlioptas, The threshold for random k-SAT is 2k ln 2 - O(k), J Am Math Soc 17 pp 947– (2004) · Zbl 1093.68075 · doi:10.1090/S0894-0347-04-00464-3 |
| [5] | Achlioptas, Random formulas have frozen variables, SIAM J Comput 39 pp 260– (2009) · Zbl 1185.68508 · doi:10.1137/070680382 |
| [6] | Ardelius, Exhaustive enumeration unveils clustering and freezing in random 3-SAT, Phys Rev E 78 pp 040101(R)– (2008) · doi:10.1103/PhysRevE.78.040101 |
| [7] | Dubois, A general upper bound for the satisfiability threshold of random r-SAT formulae, J Algorithms 24 pp 395– (1997) · Zbl 0883.68065 · doi:10.1006/jagm.1997.0867 |
| [8] | Dubois, Typical random 3-SAT formulae and the satisfiablity threshold, Electro Colloq Comput Complex 10 (2003) |
| [9] | Erd&0151;s, Supersaturated graphs and hypergraphs, Combinatorica 7 pp 35– (1987) |
| [10] | Friedgut, Sharp thresholds of graph proprties, and the k-SAT problem, J Amer Math Soc 12 pp 1017– (1999) · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7 |
| [11] | Friedgut, Hunting for sharp thresholds, Random Struct Algorithms 26 pp 37– (2005) · Zbl 1059.05092 · doi:10.1002/rsa.20042 |
| [12] | Frieze, Analysis of two simple heuristics on a random instance of k-SAT, J Algorithms 20 pp 312– (1996) · Zbl 0852.68038 · doi:10.1006/jagm.1996.0016 |
| [13] | Kaporis, Selecting complementary pairs of literals, Electron Notes Discrete Math 16 pp 47– (2003) · Zbl 1179.68144 · doi:10.1016/S1571-0653(04)00462-7 |
| [14] | Kirousis, Approximating the unsatisfiability threshold of random formulas, Random Struct Algorithms 12 pp 253– (1998) · Zbl 0936.68038 · doi:10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U |
| [15] | Krzakala, Gibbs states and the set of solutions of random constraint satisfaction problems, Proc Natl Acad Sci USA 104 pp 10318– (2007) · Zbl 1190.68031 · doi:10.1073/pnas.0703685104 |
| [16] | Mézard, Clustering of solutions in the random satisfiability problem, Phys Rev Lett 94 pp 197205– (2005) · doi:10.1103/PhysRevLett.94.197205 |
| [17] | Daudé, Pairs of SAT assignment in random Boolean formulae, Theoretical Computer Science 393 pp 260– (2008) · Zbl 1136.68049 · doi:10.1016/j.tcs.2008.01.005 |
| [18] | Mézard, Analytic and algorithmic solution of random satisfiability problems, Science 297 pp 812– (2002) · doi:10.1126/science.1073287 |
| [19] | Paley, A note on analytic functions in the unit circle, Proc Camb Phil Soc 28 pp 266– (1932) · JFM 58.1076.03 · doi:10.1017/S0305004100010112 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
