@incollection{AST_1976__38-39__183_0, author = {Paterson, Michael S.}, title = {An introduction to boolean function complexity}, booktitle = {Journ\'ees algorithmiques}, author = {Collectif}, series = {Ast\'erisque}, publisher = {Soci\'et\'e math\'ematique de France}, number = {38-39}, year = {1976}, pages = {183-201}, zbl = {0348.94043}, mrnumber = {443433}, language = {en}, url = {http://www.numdam.org/item/AST_1976__38-39__183_0} }

Paterson, Michael S. An introduction to boolean function complexity, inJournées algorithmiques, Astérisque, no. 38-39 (1976), pp. 183-201. http://www.numdam.org/item/AST_1976__38-39__183_0/

[1] Signed-digit number representation for fast parallel arithmetic," IRE Trans EC-10, 9, 389-400. | MR 135213

. "[2] Practical decidability," Report CU-CS-008-72 University of Colorado (1972). | Zbl 0329.02020

. "[3] Lower bounds on the size of Boolean formulas : preliminary report," Proc. 7th Ann. ACM Symp. on Th. of Computing (1975), 45-49. | Zbl 0381.94028

, and . "[4] A class of Boolean functions with linear combinational complexity," Theoretical Computer Science, 1, 2, 161-183. | Article | MR 416108 | Zbl 0322.68027

, and . "[5] On the complexity of the marriage problem," Advances in Mathematics 9, 3 (1972), 299-312. | Article | MR 388850 | Zbl 0251.05004

and . "[6] The logical complexity of geometric properties in the plane," J. ACM 17, 2 (1970), 339-347. | Article | MR 299479 | Zbl 0198.03502

. "[7] Lengths of formulas and elimination of quantifiers I," in Contributions to Mathematical Logic, K. Schutte, ed., North Holland Publ. Co., (1968), 175-188. | MR 238668 | Zbl 0191.28502

and . "[8] Reducibility among combinatorial problems," in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York (1972), 85-103. | Article | MR 378476 | Zbl 0366.68041

. "[9] Estimates of the complexity of solutions of systems of linear equations," Eng. trans. in Soviet Math Dokl. 7, 6 (1966), 1537-1540 | MR 208813 | Zbl 0208.40102

. "Estimates of the complexity of solutions of systems of linear equations," orig. Dokl. Akad. Nauk SSSR, 171, 4, 781-783. | MR 208813 | Zbl 0208.40102

. "[10] The complexity of the realization of symmetrical functions by formulae," English translation in Math. Notes of the Academy of Sciences of the USSR (1972), 70-76 | Zbl 0301.02016

. "The complexity of the realization of symmetrical functions by formulae," orig. in Matem. Zametki 11, 1, 109-120. | MR 311149 | Zbl 0301.02016

. "[11] Ob odnom metode sinteza skhem," Izv. VUZ (Radiofizika)1, 1 (1958), 120-140.

. "[12] Complexity of formula realization of functions of logical algebra," Prob. Cyb. 3, (1962), 782-811

. "Complexity of formula realization of functions of logical algebra," orig. Prob. Kibernetiki 3, 61-80. | MR 126385

. "[13] The depth of all Boolean functions," Th. of Computation Report 7, Univ. of Warwick (1975). To appear in SIAM J. on Computing. | MR 453331 | Zbl 0361.94051

and . "[14] Bounds to complexities of networks for sorting and switching," J. ACM22, 2 (1975), 195-201. | MR 383829 | Zbl 0334.94007

and . "[15] A Boolean function," Soviet Math. Dokl. 7, 4 (1966), 999-1000 | Zbl 0161.00901

. "[15] A Boolean function", orig. Dokl. Akad. Nauk SSSR 169, 4, 765-766. | MR 218148 | Zbl 0161.00901

. "[16] Circuit size is nonlinear in depth," Th. of Computation Report 8, Univ. of Warwick (1975). | MR 414247 | Zbl 0345.94026

and . "Circuit size is nonlinear in depth," To appear in Theoretical Computer Science. | MR 414247 | Zbl 0345.94026

and . "[17] A 2.5 N lower bound for the combinational complexity of Boolean functions," Proc. 7th Ann. ACM Symp. on Th. of Comp. Albuquerque (1975), 27-36. | MR 433982 | Zbl 0363.68067

. "[18] Short formulae for symmetric functions," IBM Research Report RC-5143, (1974), 15 pp.

. "[19] Information theory and the complexity of Boolean functions," submitted to Math. Systems Theory, (1976). | MR 462795 | Zbl 0364.94031

. "[20] Relations among complexity measures," in preparation. | Article | Zbl 0405.68041

and . "[21] The number of two-terminal seriesparallel networks," J. Math. and Physics 21 (1942), 83-93. | Article | MR 7511

and . "[22] The Complexity of Computing (manuscript). | Zbl 0391.68025

.[23] Computational work and time on finite machines", J. ACM 19, 4 (1972), 660-674. | Article | MR 329319 | Zbl 0251.68031

. "[24] Zwei lineare untere Schranken fuer die Komplexitaet Boolescher Funktionen," Computing 13 (1974), 155-171. | Article | MR 416114 | Zbl 0313.68033

. "[25] The combinational complexity of equivalence," to appear in Theoretical Computer Science 2. | MR 413600 | Zbl 0333.68032

. "[26] The synthesis of two-terminal switching circuits," Bell System Technical Journal 28 (1949), 59-98. | Article | MR 29860

. "[27] On time-hardware complexity tradeoffs for Boolean functions," Proc. 4th Hawaii Int. Symp. on System Sciences (1971), 525-527.

. "[28] On the time necessary to compute switching functions," IEEE Trans. Computers C-20 (1971), 104-105. | Article | Zbl 0217.53802

. "[29] On the combinational complexity of certain symmetric Boolean functions," IBM Research RC 5829 Math. (1976). | Article | MR 483707 | Zbl 0369.94016

. "[30] Inherent computational complexity of decision problems in logic and automata Theory." To appear in the series : Lecture Notes in Computer Science, Springer (1977)

and . "[30] The complexity of decision problems in automata theory and logic," by L. J. Stockmeyer, MAC TR 133, M.I.T. (1974).

and An earlier version of this appears as : "