On the gap between \(\mathit{ess}(f)\) and \(\mathit{cnf}_{-}\mathit{size}(f)\) (Q1759859)

Let \(f\) be a Boolean function of \(n\) variables. The gap studied in this paper is the ratio \(\mathit{cnf}_{-}\mathit{size}(f)/\mathit{ess}(f)\), where the numerator is the minimum number of clauses in a CNF formula representing \(f\), while the denominator is the size of the largest set of false points of \(f\), no two of which falsify the same implicate of \(f\). The authors prove the existence of a function \(f\) for which the gap equals \(\Theta(n)\) and of a function \(f\) whose gap is at least \(2^{\Theta(n)}\). The case of Horn functions is studied in more detail.