×

On the complexity of planar Boolean circuits. (English) Zbl 0816.68069

Summary: We consider planar circuits, formulas and multilective planar circuits. It is shown that planar circuits and formulas are incomparable. An \(\Omega (n \log n)\) lower bound is given for the multilective planar circuit complexity of a decision problem and an \(\Omega(n^{3/2})\) lower bound is given for the multilective planar circuit complexity of a multiple output function.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon andW. Maass, Meanders and their application in lower bounds arguments.J. Comput. System Sci. 37 (1988), 118-129. · Zbl 0664.68045 · doi:10.1016/0022-0000(88)90002-5
[2] A. E. Andreev, On a method giving larger than quadratic effective lower bounds for the complexity of ?-schemes.Vestnik Moscow Univ. Ser. 1 (Math. Mech.) 6, 1986, 73-76. (In Russian.)
[3] L. Babai, N. Nisan, andM. Szegedy, Multiparty protocols, pseudorandom generators for Logspace and time-space trade-offs.J. Comput. System Sci. 45 (1992), 204-232. · Zbl 0769.68040 · doi:10.1016/0022-0000(92)90047-M
[4] L. Babai, P. Pudlák, V. Rödl, andE. Szemerédi, Lower bounds to the complexity of symmetric Boolean functions.Theoret. Comput. Sci. 74 (1990), 313-323. · Zbl 0701.68044 · doi:10.1016/0304-3975(90)90080-2
[5] S. N. Bhatt andF. T. Leighton, A framework for solving VLSI graph layout problems.J. Comput. System Sci. 28(1984), 300-343. · Zbl 0543.68052 · doi:10.1016/0022-0000(84)90071-0
[6] O. Gabber, Z. Galil, Explicit construction of linear size superconcentrators.J. Comput. System Sci. 22 (1981), 407-420. · Zbl 0487.05045 · doi:10.1016/0022-0000(81)90040-4
[7] H. D. Gröger, A new partition lemma for planar graphs and its application to circuit complexity. InProceedings FCT 1991, ed.L. Budach,Lecture Notes in Computer Science 529, Springer-Verlag, 1991, 220-229. · Zbl 0925.05067
[8] P. Hochschild, Multiple cuts, input repetition, and VLSI complexity.Inform. Process. Lett. 24 (1987), 19-24. · Zbl 0632.68045 · doi:10.1016/0020-0190(87)90194-3
[9] Z. M. Kedem, Optimal allocation of computational resources in VLSI. InProc. 23rd Ann. IEEE Symp. Found. Comput. Sci., 1982, 379-385.
[10] Z. M. Kedem andA. Zorat, Replication of inputs may save computational resources in VLSI. InVLSI Systems and Computations, ed.H. T. Kung, R. Sproull, andG. Steele. Comput. Sci. Press, Rockwille MD, 1981, 52-60.
[11] Z. M. Kedem and A. Zorat, On relations between input and communication/computation in VLSI. InProc. 22nd Ann. IEEE Symp. Found. Comput. Sci., 1981, 37-41.
[12] R. J. Lipton and R. Sedgewick, Lower bounds for VLSI. InProc. Thirteenth Ann. ACM Symp. Theor. Comput., 1981, 300-307.
[13] R. J. Lipton andR. E. Tarjan, A planar separator theorem.SIAM J. Appl. Math. 36 (1979), 177-189. · Zbl 0432.05022 · doi:10.1137/0136016
[14] R. J. Lipton andR. E. Tarjan, Applications of a planar separator theorem.SIAM J. Comput. 9 (1980), 615-626. · Zbl 0456.68077 · doi:10.1137/0209046
[15] W. Maass, G. Schnitger, and E. Szemerédi, Two tapes are better than one for off-line Turing machines. InProc. Nineteenth Ann. ACM Symp. Theor. Comput., 1987, 94-100.
[16] W. Maass, G. Schnitger, E. Szemerédi, G. Turán, Two tapes versus one for off-line Turing machines.Comput complexity 3 (1993), 392-401. · Zbl 0802.68048 · doi:10.1007/BF01275490
[17] W. F. McColl, Planar crossovers.IEEE Trans. Comput. 30 (1981), 223-225. · Zbl 0455.94045 · doi:10.1109/TC.1981.1675758
[18] W. F. McColl, On the planar monotone computation of threshold functions. InProc. 2nd Symp. Theoret. Aspects of Comput. Sci., ed.K. Mehlhorn,Lecture Notes in Computer Science 182, Springer-Verlag, 1985, 219-230. · Zbl 0567.94016
[19] W. F. McColl, Planar circuits have short specifications. InProc. 2nd Symp. Theoret. Aspects of Comput. Sci., ed.K. Mehlhorn,Lecture Notes in Computer Science 182, Springer-Verlag, 1985, 231-242. · Zbl 0567.94015
[20] W. F. McColl, M. S. Paterson, The planar realization of Boolean functions.Inform. Process. Lett. 24 (1987), 165-170. · Zbl 0632.94032 · doi:10.1016/0020-0190(87)90180-3
[21] E. J. Nechiporuk, A Boolean function.Dokl. Akad. Nauk SSSR 169 (1966), 765-766. · Zbl 0161.00901
[22] W. J. Paul, A 2.5n lower bound on the combinational complexity of Boolean functions.SIAM J. Comput. 6 (1977), 427-443. · Zbl 0358.68081 · doi:10.1137/0206030
[23] J. E. Savage, Planar circuit complexity and the performance of VLSI algorithms. InVLSI Systems and Computations, ed.H. T. Kung, R. Sproull, andG. Steele. Comput. Sci. Press Rockwille MD, 1981, 61-67. Also in INRIA Report77 (1981).
[24] J. E. Savage, The performance of multilective VLSI algorithms.J. Comput. System Sci. 29 (1984), 243-272. · Zbl 0583.68021 · doi:10.1016/0022-0000(84)90033-3
[25] G. Turán, Lower bounds for synchronous circuits and planar circuits.Inform. Process. Lett. 30 (1989), 37-40. · Zbl 0662.94021 · doi:10.1016/0020-0190(89)90172-5
[26] G. Turán, On restricted Boolean circuits. InProceedings FCT 1989, ed.J. Csirik, J. Demetrovics, and F. Gécseg,Lecture Notes in Computer Science 380, Springer-Verlag, 1989, 460-469.
[27] J. D. Ullman,Computational Aspects of VLSI. Comput. Sci. Press, Rockwille MD, 1984. · Zbl 0539.68021
[28] J. Vuillemin, A combinatorial limit to the computing power of VLSI circuits.IEEE Trans. Comput. 32 (1983), 294-300. · doi:10.1109/TC.1983.1676221
[29] I. Wegener, The Complexity of Boolean Functions.Wiley-Teubner Series in Comput. Sci., 1987. · Zbl 0623.94018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.