Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Clustering of solutions in hard satisfiability problems
RISE, Swedish ICT, SICS.
RISE, Swedish ICT, SICS.
2007 (English)In: Journal of Statistical Mechanics: Theory and Experiment, ISSN 1742-5468, E-ISSN 1742-5468Article in journal (Refereed) Published
Abstract [en]

We study the structure of the solution space and behavior of local search methods on random 3-SAT problems close to the SAT/UNSAT transition. Using the overlap measure of similarity between different solutions found on the same problem instance we show that the solution space is shrinking as a function of alpha. We consider chains of satisfiability problems, where clauses are added sequentially. In each such chain, the overlap distribution is first smooth, and then develops a tiered structure, indicating that the solutions are found in well separated clusters. On chains of not too large instances, all solutions are eventually observed to be in only one small cluster before vanishing. This condensation transition point is estimated to be alpha_c = 4.26. The transition approximately obeys finite-size scaling with an apparent critical exponent of about 1.7. We compare the solutions found by a local heuristic, ASAT, and the Survey Propagation algorithm up to alpha_c.

Place, publisher, year, edition, pages
2007, 1.
Keyword [en]
finite-size scaling, energy landscapes (experiment), network dynamics, random graphs, networks
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-22379DOI: 10.1088/1742-5468/2007/10/P10012OAI: oai:DiVA.org:ri-22379DiVA: diva2:1041924
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2017-08-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full texthttp://www.iop.org/EJ/abstract/1742-5468/2007/10/P10012
By organisation
SICS
In the same journal
Journal of Statistical Mechanics: Theory and Experiment
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 20 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
v. 2.27.0