Random subcubes as a toy model for constraint satisfaction problems

abstract-Many hard combinatorial problems, such as Random Satisfiability, have been shown to reproduce some salient properties of glassy materials. In particular, it has been proved that the configurational landscapes of the hardest problems are made of many disconnected ergodic components, leading to rich phase diagrams. Here we present an exactly solvable random-subcube model inspired by the structure of hard constraint satisfaction and optimization problems. Our model reproduces the structure of the solution space of the random satisfiability and coloring problems, and undergoes the same phase transitions. Distance properties, and their relation to ergodicity, are studied. The model can also be generalized to define a continuous energy landscape useful for studying several aspects of glassy dynamics.