A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming. (English) Zbl 1356.68113
Summary: We study the probabilistic behaviour of solutions of random instances of the Boolean Satisfiability (SAT) and Constraint Satisfaction Problems (CSPs) that generalize the standard notion of a satisfying assignment. Our analysis focuses on a special type of generalized solutions, the \((1,0)\)-super solutions. For random instances of \(k\)-SAT, we establish the exact threshold of the phase transition of the solution probability for \(k \leq 3\), and give upper and lower bounds on the threshold of the phase transition for the case of \(k \geq 4\). For CSPs, we derive an upper bound on the threshold of having a \((1,0)\)-super solution asymptotically with probability 1, and establish a condition for the expected number of super solutions to grow exponentially.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
Keywords:
generalized solution concepts; super solutions; satisfiability; constraint satisfaction; random instances; probabilistic method; threshold phenomenaReferences:
| [1] | Achlioptas, D.; Moore, C., The asymptotic order of the random k-SAT threshold, (Proceedings of the 43th Annual Symposium on Foundations of Computer Science. Proceedings of the 43th Annual Symposium on Foundations of Computer Science, FOCS’02 (2002)), 779-788 |
| [2] | Achlioptas, D.; Peres, Y., The threshold for random k-SAT is \(2 k(l n 2 - o(k))\), (Proceedings of the 35th Annual ACM Symposium on Theory of Computing. Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC’03 (2003)), 223-231 · Zbl 1192.68333 |
| [3] | Alon, N.; Kahale, N., A spectral technique for coloring random 3-colorable graphs, SIAM J. Comput., 26, 1733-1748 (1997) · Zbl 0884.05042 |
| [4] | Alon, N.; Spencer, J., The Probabilistic Method (2008), Wiley · Zbl 1148.05001 |
| [5] | Beck, J., An algorithmic approach to the Lovász local lemma (I), Random Structures Algorithms, 2, 4, 343-365 (1991) · Zbl 0756.05080 |
| [6] | Chvátal, M.; Reed, B., Mick gets some (the odds are on his side), (Proceedings of 33rd Annual Symposium on Foundations of Computer Science (1992), IEEE), 620-627 · Zbl 0977.68538 |
| [7] | Combes, C., Cluster analysis of patients suffering from addictions, (Trends in Practical Applications of Heterogeneous Multi-Agent Systems (2014), Springer), 69-77 |
| [8] | Creignou, N.; Daude, H., Combinatorial sharpness criterion and phase transition classification for random CSPs, Inform. and Comput., 190, 2, 220-238 (2004) · Zbl 1085.68151 |
| [9] | Culberson, J.; Gao, Y.; Anton, C., Phase transitions of dominating clique problem and their implications to heuristics in satisfiability search, (Proceedings of the 19th International Joint Conference on Artificial Intelligence. Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI’05 (2005)), 78-83 |
| [10] | Culberson, J.; Gent, I., Frozen development in graph coloring, Theoret. Comput. Sci., 265, 1-2, 227-264 (2001) · Zbl 0983.68145 |
| [11] | Campos, V., The b-chromatic index of graphs, Discrete Appl. Math., 338, 11, 2072-2079 (2015) · Zbl 1314.05062 |
| [12] | Gao, Y.; Culberson, J., Consistency and random constraint satisfaction models, J. Artificial Intelligence Res., 28, 517-557 (2007) · Zbl 1182.68239 |
| [13] | Ginsberg, M.; Parkes, A.; Roy, A., Supermodels and robustness, (Proceedings of the 15th National Conference of American Association for Artificial Intelligence. Proceedings of the 15th National Conference of American Association for Artificial Intelligence, AAAI’98 (1998)), 334-339 |
| [14] | Gomes, C.; Walsh, T., Randomness and structure, (Rossi, F.; van Beek, P.; Walsh, T., Handbook of Constraint Programming (2006), Elsevier), 639-664 · Zbl 1175.90011 |
| [15] | Hebrard, E.; Hnich, B.; Walsh, T., Super solutions in constraint programming, (Proceedings of First International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Proceedings of First International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR’04 (2004)), 157-172 · Zbl 1094.68645 |
| [16] | Irving, R.; Manlove, D., The b-chromatic number of a graph, Discrete Appl. Math., 91, 127-141 (1999) · Zbl 0933.05051 |
| [17] | Khanna, S.; Motwani, R.; Suda, M.; Vazirani, U., On syntactic versus computational views of approximability, SIAM J. Comput., 28, 1, 164-191 (1999) · Zbl 0915.68068 |
| [18] | Manlove, D., Minimaximal and maximinimal optimisation problems: a partial order based approach (1998), Computing Science, Univeristy of Glasgow, PhD thesis |
| [19] | Xu, K.; Boussemart, F.; Hemery, F.; Lecoutre, C., Random constraint satisfaction: easy generation of hard (satisfiable) instances, Artificial Intelligence, 171 (2007) · Zbl 1168.68554 |
| [20] | Xu, K.; Li, W., Exact phase transitions in random constraint satisfaction problems, J. Artificial Intelligence Res., 12, 93-103 (2000) · Zbl 0940.68099 |
| [21] | Xu, K.; Li, W., Many hard examples in exact phase transitions, Theoret. Comput. Sci., 355, 291-302 (2006) · Zbl 1088.68163 |
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.
