Thresholds.hpp File Reference

Plans regarding boolean threshold functions. More...

Go to the source code of this file.

Detailed Description

Plans regarding boolean threshold functions.

General threshold functions
  • With [Knuth, Vol. 4, Fascicle 0, Section 7.1.1] we consider the threshold functions f(x_1, ..., x_n) = 1 iff w_1 * x_1 + ... + w_n * x_n >= t for integer constants w_i.
  • As constraints, these conditions are also known as "pseudo-boolean constraints".
  • Since we are interested for example in CNF- and DNF-representations, we also consider the negations, which (essentially) can be represented by allowing "<=" instead of ">=". How to call them? The above as "upper" threshold functions, while these as "lower" threshold functions?
  • Naming: threshold_bf(W), lthreshold_bf(W).
  • However, likely the CNF/DNF-representations should be handled in module PseudoBoolean; see Satisfiability/Lisp/PseudoBoolean/plans/general.hpp.
Cardinality constraints
  • Important special cases of threshold functions are obtained when using w_i = 1 for all i.
  • So the conditions are x_1 + ... + x_n >= t resp. <= t.
  • Naming: cardinality_bf(n,t) resp. lcardinality_bf(n,t).
  • For the special case t=1 we use alo_bf(n) resp. amo_bf(n).
  • Clause-set realisations are considered in Satisfiability/Lisp/PseudoBoolean/plans/CardinalityConstraints.hpp.
  • The condition x_1 + ... + x_n = t is expressed by ecardinality_bf(n,t). See "The basic symmetric functions" below.
The basic symmetric functions
  • The functions ecardinality_bf(n,t) run under different names:
    1. E_t in [Wegener 87]: "exactly-t-function".
    2. S_t(x_1,...,x_n) in [Knuth, Volume 4, Fascicle 0]: "basic symmetric functions".
    It seems there is no generally accepted name for them. How do we call them?
  • From these basic symmetric functions every symmetric boolean function can be computed.
    1. [Knuth] uses S_T, where T is a subset of {0,1,...,n}, to denote the symmetric function which is true iff the number of ones of the input is an element of T. (Actually, [Knuth] uses a list T, which we better replace by a set.)
    2. By the S_T we uniquely represent all 2^n symmetric functions.
  • Section 3.4 in [Wegener] presents short circuits for the basic symmetric functions.
    1. Only one output is considered, i.e., the type is [n,1].
  • All n+1 basic symmetric functions together are represented by Shannon's "symmetric switching cicuit".
    1. This boolean function is of type [n,n+1], where the output j is the ecardinality_bf(n,j).
    2. We need to find literature on that.
    3. The circuit is of size O(n^2); are there better ways? Apparently not.
    4. The easiest representation seems to be as a boolean branching program with n+1 output nodes (for the possible count-values), using a staircase-grid-structure.

Definition in file Thresholds.hpp.