Analysis of Algorithms for the Evaluation of Monotonic Boolean Functions

Abstract

This correspondence considers the efficiency of some algorithms for the evaluation of monotonic Boolean functions. It is shown that algorithms based on the criterion of maximizing the local information gain about the Boolean function with n variables may sometimes require a number of computational steps which is n/log n times the computational steps of the optimal algorithm. Copyright © 1978 by The Institute of Electrical and Electronics Engineers, Inc.