| |
A linear pseudo-Boolean constraint (LPB) is an expression of the form
a1 V l1 + ... + an V ln V d,
where each i is a literal (it assumes the value 1 or 0 depending on whether a
propositional variable xi is true or false) and a1, ..., an, d are
natural numbers. An LPB is a generalisation of a propositional clause, on
the other hand it is a restriction of integer linear programming. It has
been said that LPBs can be used to represent Boolean functions more compactly
than the well-known conjunctive or disjunctive normal forms. At one extreme,
there are those Boolean functions that can be represented as a single LPB,
the so-called threshold functions. The problem of finding, given a Boolean
function represented as a DNF, an LPB representation of this function if
possible, is called threshold recognition problem or threshold synthesis
problem. The problem is known to have an O(n7m5)
algorithm using linear programming, where n is the dimension and m the
number of terms in the DNF. It has been an open question for decades whether
it is possible to recognise threshold functions through an entirely
combinatorial procedure, i.e., without resorting to the equivalent linear
program. I have developed a procedure for doing this, which works by
decomposing the DNF and "counting" the variable occurrences in it an
appropriate way. I will present this procedure and discuss its correctness.
|
