umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, 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
Identifiers
URN: urn:nbn:se:umu:diva-38342DOI: 10.1103/PhysRevE.82.061109OAI: oai:DiVA.org:umu-38342DiVA: diva2:375333
Available from: 2010-12-09 Created: 2010-12-07 Last updated: 2017-12-11Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full texthttp://link.aps.org/doi/10.1103/PhysRevE.82.061109

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: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics

Search outside of DiVA

GoogleGoogle Scholar
Total: 72 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 63 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf