Complexity.hpp File Reference

Plans regarding complexity measurement of boolean functions (and generalisations) More...

Go to the source code of this file.

Detailed Description

Plans regarding complexity measurement of boolean functions (and generalisations)

Complexity measurements
  • For a boolean function f (or a finite function) an important task is to measure the complexity mu(f) w.r.t. some measure mu, which typically measures the size of some representation of f.
  • Important examples w.r.t. clause-representations:
    1. number of prime implicates and prime implicants
    2. more generally, the minimum number of clauses of an r_k-base of the set of prime implicates (also accordingly for the prime implicants)
    3. the minimum number of clauses in a CNF or DNF representation ( included in the above for k large enough)
    4. the minimum size of a hitting CNF/DNF
    5. the minimum size of tree-hitting CNF/DNF.
    One can also consider to minimise the sum of these CNF/DNF pairs.
  • Important examples w.r.t. circuit-representations:
    1. the minimum number of nodes in a representation w.r.t. some base
    2. important examples are the boolean base {not,and,or} and the full binary base (all 16 binary functions).
Complexity functions in dependency on n
  • For each complexity measure mu(f) of a boolean function we should consider the natural number mu(n), this maximum of mu(f) where f is a boolean function with n inputs.
  • We need naming schemes.
  • We need systems for handling concrete values (including upper and lower bounds).
  • We need to incorporate general bounds.
  • We should also have information on the boolean function which attain the maximum.

Definition in file Complexity.hpp.