[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A nonlinear lower bound on the practical combinational complexity

  • Conference paper
  • First Online:
STACS 92 (STACS 1992)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 577))

Included in the following conference series:

  • 134 Accesses

Abstract

An infinite sequence F={fn} ∞n=1 of one-output Boolean functions with the following three properties is constructed:

  1. (1)

    f n can be computed by a Boolean circuit with O(n) gates.

  2. (2)

    For any positive, nondecreasing, and unbounded function h : N → R, each Boolean circuit having an n/h(n) separator requires nonlinear number of gates to compute f n .

  3. (3)

    Each planar Boolean circuit requires Ω(n2) gates to compute f n .

Thus, one can say that f n has linear combinational complexity and a nonlinear practical combinational complexity because the constant-degree parallel architectures used in practice have their separators in O(n/log2 n).

Supported in part DFG-Grant DI 412/2-1.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aho, A.V.-Ullman, J.D.-Yannakakis, M.: On notions of information transfer in VLSI circuits. In: Proc. 15th ACM STOC, ACM Press 1983, pp. 133–139.

    Google Scholar 

  2. Blum, N.: A Boolean function requiring 3n networksize. Theoretical Computer Science 28 (1984), pp. 337–345.

    Google Scholar 

  3. Brooks, R.L.: On coloring the nodes of network. In: Proc. Cambridge Philos. Soc. 37 (1941), 194–197.

    Google Scholar 

  4. Gaber-Galil, Z.: Explicit constructions of linear-sized superconcentrators. J. Comp. Syst. Sci. 22 (1981), 407–420.

    Google Scholar 

  5. Harper, L.H.-Savage, J.E.: Complexity made Simple. In: Proc. of the Intern. Symp. on Combinatorial Theory, Rom, Sept. 1973, pp. 2–15.

    Google Scholar 

  6. Harper, L.H.-Hsiek, W.N.-Savage, J.E.: A class of Boolean functions with linear combitional complexity. Theoretical Computer Science 1, No. 2 (1975), pp. 161–183.

    Google Scholar 

  7. Hromkovič, J.: The advantages of a new approach to defining the communication complexity of VLSI. Theor. Comp. Science 57 (1988), 97–111.

    Google Scholar 

  8. Hromkovič, J.: Some complexity aspects of VLSI computations. Part 1. A framework for the study of information transfer in VLSI circuits. Computers and Artificial Intelligence 7 (1988), No. 3, pp. 229–252.

    Google Scholar 

  9. Hromkovič, J.: Some complexity aspects of VLSI computations. Part 6. Communication complexity. Computers and Artificial Intelligence 8 (1989), No. 3, pp. 209–225.

    Google Scholar 

  10. Hr90 Hromkovič, J.: Nonlinear lower bounds on the number of processors of circuits with sublinear separators. Information and Computation, to appear.

    Google Scholar 

  11. Kumičáková-Jirásková, G.: Chomsky hierarchy and communication complexity. J. Inf. Process. Cybern. EIK 25 (1989), No. 4, 157–164.

    Google Scholar 

  12. Kloss, B.M.-Malyshev, V.A.: Bounds on complexity of some classes of functions. Vest. Mosk. Univ., Seria matem., mech., 1965, No. 4, pp. 44–51 (in Russian).

    Google Scholar 

  13. Lipton, R.J.-Sedgewick, R.: Lower bounds for VLSI. In: Proc. ACM STOC'81, ACM 1981, pp. 300–307.

    Google Scholar 

  14. Lipton, R.J.-Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979), No. 2, pp. 177–189.

    Google Scholar 

  15. Lozkin, C.A.-Rybko, A.N.-SapoŽenko, A.A.-Hromkovič, J.-škalikova, N.A.: On a approach to a bound on the area complexity of combinational circuits. In: Mathematical problems in computation theory. Proc. of the Banach Center Publications. Warsaw 1988, pp. 501–510 (in Russian), the full version of this paper is accepted for publication in Theor. Comp. Sci.

    Google Scholar 

  16. Lupanov, O.B.: Ob odnom metode siteza skhem (zv. VUZ radiofizika) 1 (1958), pp. 120–140 (in Russian).

    Google Scholar 

  17. McColl: Planar circuits have short specifications. In: Proc. 2nd STACS'85, Lecture Notes in Computer Science 18, Springer-Verlag 1985, pp. 231–242.

    Google Scholar 

  18. McColl-Paterson, M.P.: The planar realization of Boolean functions. Technical Report, University of Warwick 1984.

    Google Scholar 

  19. Paul, W.J.: A 2,5n — lower bound on the combinational complexity of Boolean functions. SIAM J. Comp. 6 (1977), pp. 427–443.

    Google Scholar 

  20. Papadimitriou, Ch.-Sipser, M.: Communication complexity. J. Computer System Sci. 28 (1984), pp. 260–269.

    Google Scholar 

  21. Redkin, N.P.: Proof of minimality of circuits consisting of functional elements. Problemy kibernetiki 38 (1981), pp. 181–216 (in Russian).

    Google Scholar 

  22. Schnorr, G.P.: Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen. Computing 13 (1974), pp. 155–171.

    Google Scholar 

  23. Schnorr, G.P.: A 3 · n lower bound on the network complexity of Boolean functions. Theor. Comp. Science 10 (1980), pp. 83–92.

    Google Scholar 

  24. Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell System Techn. J. 28 (1949), pp. 59–98.

    Google Scholar 

  25. Sopranenko, E.P.: Minimal realizations of functions by circuits using functional elements. Probl. Kibernetiki 15 (1965), pp. 117–134 (in Russian).

    Google Scholar 

  26. Turán, G.: Lower bounds for synchronous circuits and planar circuits. Infor. Proc. Lett. 30 (1989), pp. 37–40.

    Google Scholar 

  27. Ullman, J.: Computational Aspects of VLSI. Principles of Computer Science Series. Computer Science Press 1984.

    Google Scholar 

  28. Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science, John Wiley and Sons Ltd., and B.G. Teubner, Stuttgart 1987.

    Google Scholar 

  29. Yao, A.C.: The entropic limitation of VLSI computations. In: Proc. 13th Annual ACM STOC, ACM 1981, pp. 308–311.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departement of Mathematics and Computer Science, University of Paderborn, Postfach 1621, 4790, Paderborn, Germany

    Juraj Hromkovič

  2. Department of Computer Science, Comenius University, 842 15, Bratislava, čSFR

    Xaver Gubáš

  3. Computer Science Institute of the Comenius University, 842 15, Bratislava, čSFR

    Juraj Waczulík

Authors
  1. Xaver Gubáš
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juraj Hromkovič
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Juraj Waczulík
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Alain Finkel Matthias Jantzen

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gubáš, X., Hromkovič, J., Waczulík, J. (1992). A nonlinear lower bound on the practical combinational complexity. In: Finkel, A., Jantzen, M. (eds) STACS 92. STACS 1992. Lecture Notes in Computer Science, vol 577. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55210-3_191

Download citation

  • DOI: https://doi.org/10.1007/3-540-55210-3_191

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-55210-9

  • Online ISBN: 978-3-540-46775-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation