TY - JOUR

T1 - On the gap between ess(f) and cnf -size(f)

AU - Hellerstein, Lisa

AU - Kletenik, Devorah

N1 - Funding Information:
This work was partially supported by the US Department of Education GAANN grant P200A090157 , and by NSF Grant CCF-0917153 .

PY - 2013/1

Y1 - 2013/1

N2 - 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 a lower bound on cnf -size(f) (the minimum number of clauses in a CNF formula for f), Čepek et al. showed it is not, in general, a tight lower bound [6]. They gave examples of functions f for which there is a small gap between ess(f) and cnf -size(f). We demonstrate significantly larger gaps. We show that the gap can be exponential in n for arbitrary Boolean functions, and Θ(√n) for Horn functions, where n is the number of variables of f. We also introduce a natural extension of the quantity ess(f), which we call essk(f), which is the largest set of assignments, no k of which falsify a common implicate of f.

AB - 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 a lower bound on cnf -size(f) (the minimum number of clauses in a CNF formula for f), Čepek et al. showed it is not, in general, a tight lower bound [6]. They gave examples of functions f for which there is a small gap between ess(f) and cnf -size(f). We demonstrate significantly larger gaps. We show that the gap can be exponential in n for arbitrary Boolean functions, and Θ(√n) for Horn functions, where n is the number of variables of f. We also introduce a natural extension of the quantity ess(f), which we call essk(f), which is the largest set of assignments, no k of which falsify a common implicate of f.

KW - CNF

KW - DNF

KW - Ess(f)

KW - Formula size

KW - Horn functions

UR - http://www.scopus.com/inward/record.url?scp=84869084290&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84869084290&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2012.07.004

DO - 10.1016/j.dam.2012.07.004

M3 - Article

AN - SCOPUS:84869084290

VL - 161

SP - 19

EP - 27

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1-2

ER -