Spines of random constraint satisfaction problems: definition and connection with computational complexity
From MaRDI portal
Abstract: We study the connection between the order of phase transitions in combinatorial problems and the complexity of decision algorithms for such problems. We rigorously show that, for a class of random constraint satisfaction problems, a limited connection between the two phenomena indeed exists. Specifically, we extend the definition of the spine order parameter of Bollobas et al. to random constraint satisfaction problems, rigorously showing that for such problems a discontinuity of the spine is associated with a resolution complexity (and thus a complexity of DPLL algorithms) on random instances. The two phenomena have a common underlying cause: the emergence of ``large (linear size) minimally unsatisfiable subformulas of a random formula at the satisfiability phase transition. We present several further results that add weight to the intuition that random constraint satisfaction problems with a sharp threshold and a continuous spine are ``qualitatively similar to random 2-SAT. Finally, we argue that it is the spine rather than the backbone parameter whose continuity has implications for the decision complexity of combinatorial problems, and we provide experimental evidence that the two parameters can behave in a different manner.
Recommendations
- The Resolution Complexity of Random Constraint Satisfaction Problems
- On the solution-space geometry of random constraint satisfaction problems
- On the solution-space geometry of random constraint satisfaction problems
- Bounds for random constraint satisfaction problems via spatial coupling
- Spanning trees in random satisfiability problems
- Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
- Resolution complexity of random constraint satisfaction problems: Another half of the story
- The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
- scientific article; zbMATH DE number 1002207
- Randomized approximation of the constraint satisfaction problem
Cites work
- scientific article; zbMATH DE number 1254648 (Why is no real title available?)
- scientific article; zbMATH DE number 1305521 (Why is no real title available?)
- scientific article; zbMATH DE number 1369843 (Why is no real title available?)
- scientific article; zbMATH DE number 1380613 (Why is no real title available?)
- scientific article; zbMATH DE number 1860652 (Why is no real title available?)
- Coloring random graphs
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- Extremal optimization of graph partitioning at the percolation threshold
- Frozen development in graph coloring
- Many hard examples for resolution
- Models and thresholds for random constraint satisfaction problems
- Nature's way of optimizing
- On the weak pigeonhole principle
- Sharp thresholds of graph properties, and the $k$-sat problem
- Short proofs are narrow—resolution made simple
- Statistical mechanics methods and phase transitions in optimization problems
- The Resolution Complexity of Random Constraint Satisfaction Problems
- The efficiency of resolution and Davis-Putnam procedures
- The phase transition in 1-in-\(k\) SAT and NAE 3-SAT
Cited in
(4)
This page was built for publication: Spines of random constraint satisfaction problems: definition and connection with computational complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q812393)
