The DNF exception problem

摘要

Given a disjunctive normal form (DNF) expression φ and a set A of vectors satisfying the expression, called the set of exceptions, we would like to update φ to get a new DNF which is false on A, and otherwise is equivalent to φ. Is there an algorithm with running time polynomial in the number of variables, the size of the original formula and the number of exceptions, which produces an updated formula of size bounded by a certain type of function of the same parameters? We give an efficient updating algorithm, which shows that the previously known best upper bound for the size of the updated expression is not optimal in order of magnitude. We then present a lower bound for the size of the updated formula in terms of the parameters, which is the first known lower bound for this problem. We also consider the special case (studied previously in the complexity theory of disjunctive normal forms) where the initial formula is identically true, and give efficient updating algorithms, providing new upper bounds for the size of the updated expression.