Horn upper bounds of random 3-CNF: a computational study
Marina Langlois, Robert H. Sloan, György Turán · 2008
Experiments are reported with computing various Horn upper bounds of random 3-CNF formulas of different densities (i.e., clause to variable ratios). Among four algorithms tested, the most successful one uses renaming of variables, and generates Horn implicates of limited size only. The output sizes and approximation errors exhibit unimodal patterns with maxima in some intermediate range of densities.