Phase transition in a random NK landscape model

DOI10.1016/j.artint.2007.06.002zbMath1182.68230OpenAlexW2085647670MaRDI QIDQ2389618

Jeong Han Kim, Sung-Soon Choi, Kyomin Jung

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 transitionsatisfiability problemfitness functionsolubilityNK landscape

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Rigorous results for the NK model.
• Estimating some features of \(NK\) fitness landscapes.
• Differential equations for random processes and random graphs
• Global optima results for the Kauffman \(NK\) model
• New global optima results for the Kauffman \(NK\) model: Handling dependency
• The scaling window of the 2-SAT transition
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Sharp thresholds of graph properties, and the $k$-sat problem
• Landscapes: Complex optimization problems and biopolymer structures
• Adaptation on Rugged Landscapes
• Bounding the unsatisfiability threshold of random 3-SAT
• Lower bounds for random 3-SAT via differential equations

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