Threshold behaviors of a random constraint satisfaction problem with exact phase transitions. (English) Zbl 1260.68166
Summary: We consider a random constraint satisfaction problem named model RB, which exhibits a sharp satisfiability phase-transition phenomenon when the control parameters pass through the critical values denoted by \(r_{cr}\) and \(p_{cr}\). Using finite-size scaling analysis, we bound the width of the transition region for finite problem size \(n\), which might be the first rigorous study on the threshold behaviors of NP-complete problems.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
constraint satisfaction problem; model RB; phase transition; finite-size scaling; threshold behavior; computational complexityReferences:
| [1] | S.A. Cook, The complexity of theorem-proving procedures, in: Proceedings of 3rd ACM Symposium on Theory of Computing, 1971, pp. 151-158.; S.A. Cook, The complexity of theorem-proving procedures, in: Proceedings of 3rd ACM Symposium on Theory of Computing, 1971, pp. 151-158. · Zbl 0253.68020 |
| [2] | V. Chvátal, B. Reed, Mick gets some (the odds are on his side), in: Proceedings of 33rd Symposium on the Foundations of Computer Science, 1992, pp. 620-627.; V. Chvátal, B. Reed, Mick gets some (the odds are on his side), in: Proceedings of 33rd Symposium on the Foundations of Computer Science, 1992, pp. 620-627. · Zbl 0977.68538 |
| [3] | Goerdt, A., A remark on random 2-SAT, Discrete Appl. Math., 96-97, 107-110 (1999) · Zbl 0937.68148 |
| [4] | Verhoeven, Y., Random 2-SAT and unsatisfiability, Inform. Process. Lett., 72, 119-123 (1999) · Zbl 0999.68086 |
| [5] | Kirkpatrick, S.; Selman, B., Critical behavior in the satisfiability of random boolean expressions, Science, 264, 1297-1301 (1994) · Zbl 1226.68097 |
| [6] | Bollobás, B.; Borgs, C.; Chayes, J.; Kim, J. H.; Wilson, D. B., The scaling window of the 2-SAT transition, Random Structures Algorithms, 18, 201-256 (2001) · Zbl 0979.68053 |
| [7] | Mertens, S.; Mézard, M.; Zecchina, R., Threshold values of random \(K\)-SAT from the cavity method, Random Structures Algorithms, 28, 340-373 (2006) · Zbl 1094.68035 |
| [8] | Xu, K.; Li, W., Exact phase transitions in random constraint satisfaction problems, J. Artificial Intelligence Res., 12, 93-103 (2000) · Zbl 0940.68099 |
| [9] | Xu, K.; Li, W., Many hard examples in exact phase transitions, Theoret. Comput. Sci., 355, 291-302 (2006) · Zbl 1088.68163 |
| [10] | Xu, K.; Boussemart, F.; Hemery, F.; Lecoutre, C., Random constraint satisfaction: easy generation of hard (satisfiable) instances, Artificial Intelligence, 171, 514-534 (2007) · Zbl 1168.68554 |
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.
