Random 2-SAT: results and problems

AbstractIn the random 2-SAT problem, we are given a set C of m disjunctions of two literals chosen at random within the (2n2) pairs of distinct literals coming from n logical variables. The basic problem is to find out for which values of the ratio ρ=m/n the disjunctions in C are almost surely simultaneously satisfiable (or almost surely not simultaneously satisfiable) as n tends to infinity. The purpose of this paper is to review the main steps in the solution of this problem, starting with the location of the asymptotic critical ratio around 8 years ago and ending with the recent almost complete solution due to Bollobás et al. Thus, this paper is not a review in the usual sense of the word, i.e., it does not include all the known results about random 2-SAT. We will also make a few comments concerning the behaviour of the number of satisfying assignments of random instances of 2-SAT below the critical ratio, a problem relevant to theoretical physics