Optimal myopic algorithms for random 3-SAT

Abstract

Let F3(n, m) be a random 3-SAT formula formed by selecting uniformly, independently, and with replacement, m clauses among all 8(3n) possible 3-clauses over n variables. It has been conjectured that there exists a constant r3 such that for any ε>0, F3(n, (r3-ε)n) is almost surely satisfiable, but F3(n, (r3+ε)n) is almost surely unsatisfiable. The best lower bounds for the potential value of r3 have come from analyzing rather simple extensions of unit-clause propagation. Recently, it was shown that all these extensions can be cast in a common framework and analyzed in a uniform manner by employing differential equations. Here, we determine optimal algorithms expressible in that framework, establishing r3>3.26. We extend the analysis via differential equations, and make extensive use of a new optimization problem we call `max-density multiple-choice knapsack'. The structure of optimal knapsack solutions elegantly characterizes the choices made by an optimal algorithm.