Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming.

Authors:
Alexander K Hartmann
Alexander K Hartmann
Universität Oldenburg

PLoS One 2019 19;14(4):e0215309. Epub 2019 Apr 19.

Institut für Physik, Universität Oldenburg, Oldenburg, Germany.

Here we study linear programming applied to the random K-SAT problem, a fundamental problem in computational complexity. The K-SAT problem is to decide whether a Boolean formula with N variables and structured as a conjunction of M clauses, each being a disjunction of K variables or their negations is satisfiable or not. The ensemble of random K-SAT attracted considerable interest from physicists because for a specific ratio αs = M/N it undergoes in the limit of large N a sharp phase transition from a satisfiable to an unsatisfiable phase. In this study we will concentrate on finding for linear programming algorithms "easy-hard" transitions between phases of different typical hardness of the problems on either side. Linear programming is widely applied to solve practical optimization problems, but has been only rarely considered in the physics community. This is a deficit, because those typically studied types of algorithms work in the space of feasible {0, 1}N configurations while linear programming operates outside the space of valid configurations hence gives a very different perspective on the typical-case hardness of a problem. Here, we demonstrate that the technique leads to one simple-to-understand transition for the well known 2-SAT problem. On the other hand we detect multiple transitions in 3-SAT and 4-SAT. We demonstrate that, in contrast to the previous work on vertex cover and therefore somewhat surprisingly, the hardness transitions are not driven by changes of any of various standard percolation or solution space properties of the problem instances. Thus, here a more complex yet undetected property must be related to the easy-hard transition.

Download full-text PDF

Source
http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0215309PLOS
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6474652PMC
April 2019

Publication Analysis

Top Keywords

linear programming
20
programming applied
8
random k-sat
8
k-sat problem
8
problem
7
linear
5
programming
5
specific ratio
4
surprisingly hardness
4
changes standard
4
phase study
4
ratio αs
4
unsatisfiable phase
4
study will
4
cover surprisingly
4
feasible 1}n
4
programming algorithms
4
finding linear
4
concentrate finding
4
will concentrate
4

References

(Supplied by CrossRef)
Computers and intractability
MR Garey et al.
1979
Dover Books on Computer Science Series
CH Papadimitriou et al.
1998
Reducibility among combinatorial problems
RM Karp et al.
1972
The Nature of Computation
C Moore et al.
2011
Gibbs states and the set of solutions of random constraint satisfaction problems
F Krzakała et al.
Proceedings of the National Academy of Sciences 2007

Similar Publications