On the gap between ess(f) and cnf_size(f)

Lisa Hellerstein, Devorah Kletenik

Given a Boolean function f, the quantity ess(f) denotes the largest set of assignments that falsify f, no two of which falsify a common implicate of f. Although ess(f)$ is clearly…