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 language | English (US) |
---|---|
State | Published - 2012 |
Event | International Symposium on Artificial Intelligence and Mathematics, ISAIM 2012 - Fort Lauderdale, FL, United States Duration: Jan 9 2012 → Jan 11 2012 |
Other
Other | International Symposium on Artificial Intelligence and Mathematics, ISAIM 2012 |
---|---|
Country/Territory | United States |
City | Fort Lauderdale, FL |
Period | 1/9/12 → 1/11/12 |
ASJC Scopus subject areas
- Artificial Intelligence
- Applied Mathematics