Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
arXiv:1702.02821 · doi:10.1371/journal.pone.0215309
Abstract
Here we study the NP-complete -SAT problem. Although the worst-case complexity of NP-complete problems is conjectured to be exponential, there exist parametrized random ensembles of problems where solutions can typically be found in polynomial time for suitable ranges of the parameter. In fact, random -SAT, with as control parameter, can be solved quickly for small enough values of . It shows a phase transition between a satisfiable phase and an unsatisfiable phase. For branch and bound algorithms, which operate in the space of feasible Boolean configurations, the empirically hardest problems are located only close to this phase transition. Here we study -SAT () and the related optimization problem MAX-SAT by a linear programming approach, which is widely used for practical problems and allows for polynomial run time. In contrast to branch and bound it operates outside the space of feasible configurations. On the other hand, finding a solution within polynomial time is not guaranteed. We investigated several variants like including artificial objective functions, so called cutting-plane approaches, and a mapping to the NP-complete vertex-cover problem. We observed several easy-hard transitions, from where the problems are typically solvable (in polynomial time) using the given algorithms, respectively, to where they are not solvable in polynomial time. For the related vertex-cover problem on random graphs these easy-hard transitions can be identified with structural properties of the graphs, like percolation transitions. For the present random -SAT problem we have investigated numerous structural properties also exhibiting clear transitions, but they appear not be correlated to the here observed easy-hard transitions. This renders the behaviour of random -SAT more complex than, e.g., the vertex-cover problem.
arXiv comment11 pages, 5 figures
References in corpus (19)
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Phase Transitions in the Coloring of Random Graphs
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Survey propagation: an algorithm for satisfiability
- Optimization hardness as transient chaos in an analog approach to constraint satisfaction
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Core percolation in random graphs: a critical phenomena analysis
- Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
- A practical guide to computer simulations
- Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
- Phase coexistence and finite-size scaling in random combinatorial problems
- Exhaustive enumeration unveils clustering and freezing in random 3-SAT
- Statistical mechanics of the vertex-cover problem
- autoScale.py - A program for automatic finite-size scaling analyses: A user's guide
- Numerical Solution-Space Analysis of Satisfiability Problems
- Phase transition for cutting-plane approach to vertex-cover problem
- Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
- Order-to-chaos transition in the hardness of random Boolean satisfiability problems