Phase transitions and the search problem

DOI10.1016/0004-3702(95)00044-5OpenAlexW2039557216MaRDI QIDQ2674173

Tad Hogg, Bernardo A. Huberman, Colin P. Williams

Publication date: 22 September 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(95)00044-5

zbMATH Keywords

phase transitionssearchconstraint satisfaction

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (24)

Search optimization, funnel topography, and dynamical criticality on the string landscape ⋮ The state of SAT ⋮ Early-time measure in eternal inflation ⋮ Configurable sublinear circuits for quantum state preparation ⋮ Experimental complexity analysis of continuous constraint satisfaction problems. ⋮ Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks ⋮ Pairs of SAT-assignments in random Boolean formulæ ⋮ A unified framework for partial and hybrid search methods in constraint programming ⋮ A new constraint test-case generator and the importance of hybrid optimizers ⋮ Quantum optimization ⋮ Statistical mechanics methods and phase transitions in optimization problems ⋮ Results related to threshold phenomena research in satisfiability: Lower bounds ⋮ Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs ⋮ A generative power-law search tree model ⋮ From decidability to undecidability by considering regular sets of instances ⋮ Complexity-theoretic models of phase transitions in search problems ⋮ An information-based neural approach to generic constraint satisfaction. ⋮ SAT distributions with planted assignments and phase transitions between decision and optimization problems ⋮ SAT Distributions with Phase Transitions between Decision and Optimization Problems ⋮ Phase transitions of subset sum and Shannon's limit in source coding ⋮ Problem difficulty for tabu search in job-shop scheduling ⋮ On market-inspired approaches to propositional satisfiability ⋮ Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability ⋮ Accessibility measure for eternal inflation: dynamical criticality and higgs metastability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• The hardest constraint problems: A double phase transition
• Exploiting the deep structure of constraint problems
• Easy problems are sometimes hard
• Searching for an optimal path in a tree with random costs
• An empirical study of phase transitions in binary constraint satisfaction problems
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Some Cluster Size and Percolation Problems
• The average complexity of depth-first search with backtracking and cutoff
• Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs
• A Parallel Graph Coloring Heuristic

This page was built for publication: Phase transitions and the search problem