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

Lisa Hellerstein, Devorah Kletenik

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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.

    Original languageEnglish (US)
    Pages (from-to)19-27
    Number of pages9
    JournalDiscrete Applied Mathematics
    Volume161
    Issue number1-2
    DOIs
    StatePublished - Jan 2013

    Keywords

    • CNF
    • DNF
    • Ess(f)
    • Formula size
    • Horn functions

    ASJC Scopus subject areas

    • Discrete Mathematics and Combinatorics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'On the gap between ess(f) and cnf -size(f)'. Together they form a unique fingerprint.

    Cite this