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

TY - CHAP AU - Paterson, Michael S. TI - An introduction to boolean function complexity BT - Journées algorithmiques AU - Collectif T3 - Astérisque PY - 1976 SP - 183 EP - 201 IS - 38-39 PB - Société mathématique de France UR - http://archive.numdam.org/item/AST_1976__38-39__183_0/ LA - en ID - AST_1976__38-39__183_0 ER -

Paterson, Michael S. An introduction to boolean function complexity, inJournées algorithmiques, Astérisque, no. 38-39 (1976), pp. 183-201. http://archive.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

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

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

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

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

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

. "[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 | Zbl

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. | DOI | MR | Zbl

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

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

. "[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

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

. "[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

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

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

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

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

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

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

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 | Zbl

. "[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 | Zbl

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

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

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

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

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

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

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

. "[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. | DOI | Zbl

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

. "[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 : "