On the Complexity of Generation of Rational Numbers by Boolean Functions.

Roman M. Kolpakov

Published in: Fundam. Informaticae (1995)

Keyphrases

boolean functions
uniform distribution
polynomial size
threshold functions
computational complexity
relevant variables
prime implicants
membership queries
multi valued
functional properties
lower bound
upper bound
worst case
binary decision diagrams
dnf formulas
linear threshold