Simplest random K-satisfiability problem.

摘要: We study a simple and exactly solvable model for the generation of random satisfiability problems. These consist $\ensuremath{\gamma}N$ boolean constraints which are to be satisfied simultaneously by N logical variables. In statistical-mechanics language, considered can seen as diluted p-spin at zero temperature. While such problems become extraordinarily hard solve local search methods in large region parameter space, still least one solution may superimposed construction. The statistical properties studied replica method each single instance analyzed polynomial time global method. geometrical topological structures responsible dynamic static phase transitions well onset computational complexity thoroughly analyzed. Numerical analysis on very samples allows precise characterization critical scaling behavior.