Schawe, Hendrik and Bleim, Roman and Hartmann, Alexander K.
(2019)
Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming.
PLOS ONE, 14 (4).
e0215309.
ISSN 19326203
Abstract
Here we study linear programming applied to the random KSAT problem, a fundamental problem in computational complexity. The KSAT 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 KSAT 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 “easyhard” 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 typicalcase hardness of a problem. Here, we demonstrate that the technique leads to one simpletounderstand transition for the well known 2SAT problem. On the other hand we detect multiple transitions in 3SAT and 4SAT. 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 easyhard transition.
Actions (login required)

View Item 