A Combinatorial Algorithm for the Threshold Recognition Problem
      - Jan-Georg Smaus

    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.

Last updated: November 7, 2009.