Symmetric and Threshold Boolean Functions Are Exhaustive
Bernard M. E. Moret, Thomason, Gonzalez Gonzalez · IEEE Transactions on Computers · 1983
The worst-case number of variable evaluations (testing cost) of Boolean functions is examined. Following up on a result by Rivest and Vuillemin, we show that all symmetric as well as all linearly separable Boolean functions are exhaustive, that is, have a pessimal worst-case testing cost.