A Boolean function requiring 3n network size

Theoretical Computer Science - Tập 28 - Trang 337-345 - 1983
Norbert Blum1
1Fachbereich 10, Universität des Saarlandes, D-6600 Saarbrücken, Fed. Rep. Germany

Tài liệu tham khảo

Blum, 1981, A 2.75n-lower bound on the network complexity of boolean functions Paul, 1977, A 2.5n-lower bound on the combinational complexity of boolean functions, SIAM J. Comput., 6, 427, 10.1137/0206030 Schnorr, 1974, Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen, Computing, 13, 155, 10.1007/BF02246615 Schnorr, 1980, A 3n-lower bound on the network complexity of boolean functions, Theoret. Comput. Sci., 10, 83, 10.1016/0304-3975(80)90074-2 Stockmeyer, 1977, On the combinational complexity of certain symmetric Boolean functions, Math. Systems Theory, 10, 323, 10.1007/BF01683282 I. Wegener, Private communication, 1981.