most citedPhase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming

10 citations · 10 across the 1 of their papers we have counts for

collaborators

1 paper

cond-mat.dis-nn2017★ 10 cited

Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming

Hendrik Schawe, Roman Bleim, Alexander K. Hartmann

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 ensemble…