SAT Temperature

SAT Temperature

Definition

Given a 3SAT formula in conjunctive normal form made of m clauses and n variables, its temperature is defined as the ratio T = m / n. The probability for a random 3SAT formula to be satisfiable tends to 1 as T tends to 0, towards 0 as T tends to infinity, and undergoes a sharp transition from 1 to 0 at T ~= 4.2.

Computing the temperature for general CNF formulaes

Let phi be a CNF formula.

phi = c_1 /\ c_2 /\ ... /\ c_m

It can be converted to a 3SAT formula with a linear increase in the formula size, as described in http://www.staff.ul.ie/burkem/ma4016n2.pdf. However, the size of the resulting 3SAT formula can be computed directly rather simply : for each clause c_i, we may add a number of extra clauses and a number of extra variables, these numbers depending only on the size of c_i, as follows :