Random 2-SAT Data

This file gives experimental data on the random 2-SAT transition. Data is given for when the number of variables is 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, or 1048576. For each number of variables n, the following experiment was done 10000 times: pick random 2-clauses one at a time with replacement, and report the number of clauses picked when the formula becomes unsatisfiable. One can plot a cumulative distribution function of these experimental thresholds to estimate the probability of satisfiability for various numbers of clauses. Comparing these distributions for various values of n, one can try to determine the asymptotic properties of the probability of satisfiability.

Empirically, the curves enter the asymptotic regime when n>=4096, and if one used only the curves for n<=1024, one would get erroneous estimates of the power law behavior of the characteristic width of the transition to unsatisfiability. This does not bode well for experimental results on random k-SAT (k>2), and indeed it was recently shown (Wilson 2000) that previous experimental estimates of the scaling behavior are wrong. Comparing the curves for all the above values of n, experimentally it is pretty clear that the exponent ``ν'' is 3±0.02. It has been rigorously proven that ν=3 (Bollobás, Borgs, Chayes, Kim, and Wilson 1999).