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.0215309 | PLOS |

http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6474652 | PMC |

April 2019

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

Computers and intractability

MR Garey et al.

1979

MR Garey et al.

1979

Dover Books on Computer Science Series

CH Papadimitriou et al.

1998

CH Papadimitriou et al.

1998

Reducibility among combinatorial problems

RM Karp et al.

1972

RM Karp et al.

1972

Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem

G Biroli et al.

*Physica A: Statistical Mechanics and its Applications* 2002

G Biroli et al.

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

F Krzakała et al.