On the Complexity of the Evaluation of Transient Extensions of Boolean Functions

Janusz A. Brzozowski Baiyu Li Yuli Ye

Published in: DCFS (2010)

Keyphrases

boolean functions
uniform distribution
polynomial size
threshold functions
relevant variables
prime implicants
read once formulas
dnf formulae
computational complexity
bounded treewidth
decision problems
bi decomposition
worst case
functional properties