The Equivalence of Horn and Network Complexity for Boolean Functions.

Stål O. Aanderaa Egon Börger

Published in: Acta Informatica (1981)

Keyphrases

boolean functions
uniform distribution
polynomial size
dnf formulae
np hard
worst case
complex networks
membership queries
linear threshold
relevant variables
threshold functions
prime implicants
disjunctive normal form