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

Computer Science – Discrete Mathematics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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), Cepek et al. showed that it is not, in general, a tight lower bound. 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 Theta(sqrt{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 ess_k(f), which is the largest set of assignments, no k of which falsify a common implicate of f.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On the gap between ess(f) and cnf_size(f) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the gap between ess(f) and cnf_size(f), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the gap between ess(f) and cnf_size(f) will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-179259

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.