Compositional complexity of Boolean functions.

Harold Abelson Andrzej Ehrenfeucht James Fickett Jan Mycielski

Published in: Discret. Appl. Math. (1982)

Keyphrases

boolean functions
uniform distribution
polynomial size
threshold functions
membership queries
dnf formulae
relevant variables
worst case
functional properties
disjunctive normal form
multi valued
binary decision diagrams
bounded treewidth
decision trees
computational complexity