2008/03/31 by Lenka Zdeborová, Marc Mézard
Computer Science · Mathematics · Physics and Astronomy · #Advanced Database Systems and Queries #Algorithm #Artificial intelligence #Backtracking #Computer science #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Constraint satisfaction #Constraint satisfaction dual problem #Constraint satisfaction problem #Data Management and Algorithms #Geometry #Local consistency #Mathematical optimization #Mathematics #Optimization problem #Phase (matter) #Phase diagram #Physics #Point (geometry) #Quantum mechanics #Space (punctuation) #Theoretical computer science #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC
paper · pdf · doi:10.1103/physrevlett.101.078702
published as Phys. Rev. Lett. 101, 078702 (2008) · 4 pages, 2 figures
openalex publication_date 2008/08/15 · arxiv created 2008/09/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We introduce and study the random "locked" constraint satisfaction problems. When increasing the density of constraints, they display a broad "clustered" phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. We thus propose new benchmarks of really hard optimization problems and provide insight into the origin of their typical hardness.