Sökning: onr:"swepub:oai:DiVA.org:kth-8492" >
Clustering of solut...
Clustering of solutions in hard satisfiability problems
-
- Ardelius, John (författare)
- RISE,SICS
-
- Aurell, Erik (författare)
- KTH,Beräkningsbiologi, CB
-
- Krishnamurthy, Supriya (författare)
- RISE,KTH,Skolan för informations- och kommunikationsteknik (ICT),SICS
-
(creator_code:org_t)
- 2007
- 2007
- Engelska.
-
Ingår i: Journal of Statistical Mechanics: Theory and Experiment. - 1742-5468. ; :10, s. P10012-
- Relaterad länk:
-
http://www.iop.org/E...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- We study numerically the solution space structure of random 3-SAT problems close to the SAT/UNSAT transition. This is done by considering chains of satisfiability problems, where clauses are added sequentially to a problem instance. Using the overlap measure of similarity between different solutions found on the same problem instance, we examine geometrical changes as a function of α. In each chain, the overlap distribution is first smooth, but then develops a tiered structure, indicating that the solutions are found in well separated clusters. On chains of not too large instances, all remaining solutions are eventually observed to be found in only one small cluster before vanishing. This condensation transition point is estimated by finite size scaling to be αc = 4.26 with an apparent critical exponent of about 1.7. The average overlap value is also observed to increase with α up to the transition, indicating a reduction in solutions space size, in accordance with theoretical predictions. The solutions are generated by a local heuristic, ASAT, and compared to those found by the Survey Propagation algorithm up to αc.
Ämnesord
- NATURVETENSKAP -- Biologi -- Bioinformatik och systembiologi (hsv//swe)
- NATURAL SCIENCES -- Biological Sciences -- Bioinformatics and Systems Biology (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Nyckelord
- Energy landscapes (experiment)
- Finite-size scaling
- Network dynamics
- Networks
- Random graphs
- Bioinformatics
- Bioinformatik
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas