Computer Science – Computational Complexity
Scientific paper
2005-03-29
Computer Science
Computational Complexity
A revised version of this paper will appear in Annals of Mathematics and Artificial Intelligence
Scientific paper
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 $2^{\Omega(n)}$ resolution complexity (and thus a $2^{\Omega(n)}$ 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.
Boettcher Stefan
Istrate Gabriel
Percus Allon G.
No associations
LandOfFree
Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-439184