Computational Complexity and Phase Transitions

Abstract

Phase transitions in combinatorial problems have recently been shown to be useful in locating "hard" instances of combinatorial problems. The connection between computational complexity and the existence of phase transitions has been addressed in Statistical Mechanics and Artificial Intelligence, but not studied rigorously. We take a step in this direction by investigating the existence of sharp thresholds for the class of generalized satisfiability problems defined by Schaefer. In the case when all constraints are clauses we give a complete characterization of such problems that have a sharp threshold. While NP-completeness does not imply (even in this restricted case) the existence of a sharp threshold, it "almost implies" this, since clausal generalized satisfiability problems that lack a sharp threshold are either 1. polynomial time solvable, or 2. predicted, with success probability lower bounded by some positive constant by across all the probability range, by a single, trivial procedure.

A (slightly) revised version of the paper submitted to the 15th IEEE Conference on Computational Complexity

References in corpus (2)

• The Scaling Window of the 2-SAT Transition
• Phase Transition in the Number Partitioning Problem

Cited by in corpus (5)

• Global optimization of quantum dynamics with AlphaZero deep exploration
• Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems
• Crossover phenomenon in the performance of an Internet search engine
• q-Overlaps in the Random Exact Cover Problem
• Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)