Change search
ReferencesLink to record
Permanent link

Direct link
Finite-size scaling in random K-satisfiability problems
Umeå University, Faculty of Science and Technology, Department of Physics.
2010 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 82, no 061109Article in journal (Refereed) Published
Abstract [en]

We provide a comprehensive view of various phase transitions in random K-satisfiability problems solved by stochastic-local-search algorithms. In particular, we focus on the finite-size scaling (FSS) exponent, which is mathematically important and practically useful in analyzing finite systems. Using the FSS theory of nonequilibrium absorbing phase transitions, we show that the density of unsatisfied clauses clearly indicates the transition from the solvable (absorbing) phase to the unsolvable (active) phase as varying the noise parameter and the density of constraints. Based on the solution clustering (percolation-type) argument, we conjecture two possible values of the FSS exponent, which are confirmed reasonably well in numerical simulations for 2≤K≤3.

Place, publisher, year, edition, pages
2010. Vol. 82, no 061109
URN: urn:nbn:se:umu:diva-38342DOI: 10.1103/PhysRevE.82.061109OAI: diva2:375333
Available from: 2010-12-09 Created: 2010-12-07 Last updated: 2010-12-09Bibliographically approved

Open Access in DiVA

fulltext(281 kB)56 downloads
File information
File name FULLTEXT01.pdfFile size 281 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Lee, Sang Hoon
By organisation
Department of Physics
In the same journal
Physical Review E. Statistical, Nonlinear, and Soft Matter Physics

Search outside of DiVA

GoogleGoogle Scholar
Total: 56 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 47 hits
ReferencesLink to record
Permanent link

Direct link