Phase transition in a random NK landscape model

DOI10.1016/J.ARTINT.2007.06.002MaRDI QIDQ2389618zbMATH OpenOpenAlexFDO

Authors Sung-Soon Choi, Kyomin Jung, Jeong Han Kim

Publication date 17 July 2009

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.artint.2007.06.002

zbMATH Keywords

phase transitionsolubilityfitness functionsatisfiability problemNK landscape

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Genetics and epigenetics (92D10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1946856
• scientific article; zbMATH DE number 1369843
• The SAT phase transition
• On the phase transitions of (k, q)-SAT
• Random instances of problems in NP -- algorithms and statistical physics

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3657493 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1946856 (Why is no real title available?)
• scientific article; zbMATH DE number 2013546 (Why is no real title available?)
• scientific article; zbMATH DE number 2040656 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• scientific article; zbMATH DE number 960162 (Why is no real title available?)
• A threshold for unsatisfiability
• Adaptation on Rugged Landscapes
• Bounding the unsatisfiability threshold of random 3-SAT
• Differential equations for random processes and random graphs
• Estimating some features of \(NK\) fitness landscapes.
• Global optima results for the Kauffman \(NK\) model
• Landscapes: Complex optimization problems and biopolymer structures
• Lower bounds for random 3-SAT via differential equations
• New global optima results for the Kauffman \(NK\) model: Handling dependency
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Rigorous results for the NK model.
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Sharp thresholds of graph properties, and the $k$-sat problem
• The scaling window of the 2-SAT transition
• The unsatisfiability threshold revisited

Cited in

(1)

• scientific article; zbMATH DE number 1946856 (Why is no real title available?)

This page was built for publication: Phase transition in a random NK landscape model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2389618)