On the gap between ess(f) and cnf fisize(f) (extended abstract)

Lisa Hellerstein, Devorah Kletenik

    Research output: Contribution to conferencePaperpeer-review

    Abstract

    Given a Boolean function f, ess(f) denotes the largest set of assignments that falsify f, no two of which falsify a common implicate of f. The quantity ess(f) is a lower bound on cnf fisize(f) (the minimum number of clauses in a CNF formula for f). Čepek et al. gave examples of functions f for which there is a small gap between ess(f) and cnf fisize(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.

    Original languageEnglish (US)
    StatePublished - 2012
    EventInternational Symposium on Artificial Intelligence and Mathematics, ISAIM 2012 - Fort Lauderdale, FL, United States
    Duration: Jan 9 2012Jan 11 2012

    Other

    OtherInternational Symposium on Artificial Intelligence and Mathematics, ISAIM 2012
    CountryUnited States
    CityFort Lauderdale, FL
    Period1/9/121/11/12

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Applied Mathematics

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

    Cite this