Simplest random K-satisfiability problem - art. no. 026702

We study a simple and exactly solvable model for the generation of random s atisfiability problems. These consist of gammaN random boolean constraints which are to be satisfied simultaneously by N logical variables. In statist ical-mechanics language, the considered model can be seen as a diluted p-sp in model at zero temperature. While such problems become extraordinarily ha rd to solve by local search methods in a large region of the parameter spac e, still at least one solution may be superimposed by construction. The sta tistical properties of the model can be studied exactly by the replica meth od and each single instance can be analyzed in polynomial time by a simple global solution method. The geometrical and topological structures responsi ble for dynamic and static phase transitions as well as for the onset of co mputational complexity in the local search method are thoroughly analyzed. Numerical analysis on very large samples allows for a precise characterizat ion of the critical scaling behavior.