Simplest random<b><i>K</i></b>-satisfiability problem
Simplest random<b><i>K</i></b>-satisfiability problem
We study a simple and exactly solvable model for the generation of random satisfiability problems. These consist of gammaN random boolean constraints which are to be satisfied simultaneously by N logical variables. In statistical-mechanics language, the considered model can be seen as a diluted p-spin model at zero temperature. While …