Hidden Threshold Phenomena for Fixed-Density SAT-formulae

摘要

Experimental evidence is presented that hidden threshold phenomena exist for fixed density random 3-SAT and graph-3-coloring formulae. At such fixed densities the average Horn fraction (computed with a specially designed algorithm) appears to be a parameter with respect to which these phenomena can be measured. This paper investigates the effects of size on the observed phenomena.