Critical Behavior in the Satisfiability of Random Boolean Expressions
作者： S. Kirkpatrick , B. Selman
DOI: 10.1126/SCIENCE.264.5163.1297
关键词:
摘要: Determining the satisfiability of randomly generated Boolean expressions with k variables per clause is a popular test for performance search algorithms in artificial intelligence and computer science. It known that = 2, formulas are almost always satisfiable when ratio clauses to less than 1; ratios larger 1, never satisfiable. Similar sharp threshold behavior observed higher values k. Finite-size scaling, method from statistical physics, can be used characterize size-dependent effects near threshold. A relationship drawn between thresholds computational complexity.
sciencemag.org
unirioja.es
harvard.edu参考文章(7)
A. P. Kamath, N. K. Karmarkar, K. G. Ramakrishnan, M. G. C. Resende, Computational experience with an interior point algorithm on the satisfiability problem Annals of Operations Research. ,vol. 25, pp. 43- 58 ,(1990) , 10.1007/BF02283686
Bengt Aspvall, Michael F. Plass, Robert Endre Tarjan, A linear-time algorithm for testing the truth of certain quantified boolean formulas☆ Information Processing Letters. ,vol. 8, pp. 121- 123 ,(1979) , 10.1016/0020-0190(79)90002-4
Martin Davis, Hilary Putnam, A Computing Procedure for Quantification Theory Journal of the ACM. ,vol. 7, pp. 201- 215 ,(1960) , 10.1145/321033.321034
Scott Kirkpatrick, Robert H. Swendsen, Statistical mechanics and disordered systems Communications of The ACM. ,vol. 28, pp. 363- 373 ,(1985) , 10.1145/3341.3344
S. H. CLEARWATER, B. A. HUBERMAN, T. HOGG, Cooperative Solution of Constraint Satisfaction Problems Science. ,vol. 254, pp. 1181- 1183 ,(1991) , 10.1126/SCIENCE.254.5035.1181
Béla Bollobás, Random Graphs ,(1985)
Amnon Aharony, Dietrich Stauffer, Introduction to percolation theory Published in <b>1992</b> in London by Taylor and Francis. ,(1992)