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 1932-6203

[img] - Published Version

Volltext (681Kb)


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.

Item Type: Article
Additional Information: Publiziert mit Hilfe des DFG-geförderten Open Access-Publikationsfonds der Carl von Ossietzky Universität Oldenburg.
Subjects: Science and mathematics > Physics
Divisions: Faculty of Mathematics and Science > Institute of Physics (IfP)
Date Deposited: 18 Mar 2020 08:33
Last Modified: 17 Apr 2020 07:46
URN: urn:nbn:de:gbv:715-oops-45475
DOI: 10.1371/journal.pone.0215309

Actions (login required)

View Item View Item

Document Downloads

More statistics for this item...