zbMATH — the first resource for mathematics

The monotone circuit complexity of Boolean functions. (English) Zbl 0631.68041
Some new results concerning lower bounds for the complexity of monotone circuits that detect cliques in graphs are obtained using modified versions of known methods. It is shown that even a very rough approximation of the maximum clique size of a graph, requires superpolynomial size of monotone circuits. Also, lower bounds are given for some Boolean functions and a largest lower bound for an NP-function of n variables is obtained.
Reviewer: L.Livovschi

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI
[1] A. V. Aho, J. E. Hopcroft, andJ. D. Ullman,The Design and Analysis of Computer Algorithms, Addison–Wesley, Reading, 1974. · Zbl 0326.68005
[2] A. E. Andreev, On a method for obtaining lower bounds for the complexity of individual monotone functions,Dokl. Ak. Nauk. SSSR 282 (1985), 1033–1037 (in Russian). English translation inSov. Math. Dokl. 31 (1985), 530–534.
[3] P. A. Bloniarz,The complexity of monotone Boolean functions and an algorithm for finding shortest paths in a graph, Ph. D. Dissertation, Technical Report238, Laboratory for Computer Science, Massachusetts Institute of Technology, 1979.
[4] N. Blum, A Boolean function requiring 3n network size,Theoretical Computer Science 28 (1984), 337–345. · Zbl 0539.94036
[5] F. Chung andR. M. Karp,in: Open problems proposed at the NSF Conf. on Complexity Theory, Eugene, Oregon 1984,SIGACT News 16 (1984), 46.
[6] P. Erdos andR. Rado, Intersection theorems for systems of sets,Journal of London Mathematical Society 35 (1960), 85–90. · Zbl 0103.27901
[7] J. E. Hopcroft andR. M. Karp, Ann 5/2 algorithm for maximum matching in bipartite graphs,SIAM Journal on Computing 4 (1973), 225–231. · Zbl 0266.05114
[8] K. Mehlhorn andZ. Galil, Monotone switching circuits and Boolean matrix product,Computing 16 (1976), 99–111. · Zbl 0323.94019
[9] J. Nešetřil andS. Poljak, On the complexity of the subgraph problem,CMUC 26 (1985), 415–419. · Zbl 0571.05050
[10] M. S. Paterson, Complexity of monotone networks for Boolean matrix products,Theoretical Computer Science 1 (1975), 13–20. · Zbl 0307.68031
[11] V. R. Pratt, The power of negative thinking in multiplying Boolean matrices,SIAM Journal on Computing 4 (1974), 326–330. · Zbl 0318.94040
[12] A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions,Dokl. Ak. Nauk. SSSR,281, (1985), 798–801 (in Russian). English translation in:Sov. Math. Dokl.,31 (1985), 354–357.
[13] A. A. Razborov, Lower bounds on monotone network complexity of the logical permanent,Mat. Zametki,37 (1985), 887–900 (in Russian). English translation in:Math. Notes of the Academy of Sciences of the USSR 37 (1985), 485–493.
[14] C. E. Shannon, The synthesis of two-terminal switching circuits,Bell System Technical Journal,28 (1949), 59–98.
[15] S. Skyum andL. G. Valiant, A complexity theory based on Boolean algebra,Journal of the ACM,32:2 (1985), 484–502. · Zbl 0633.68032
[16] J. Tiekenheinrich, A 4n-lower bound on the monotone network complexity of a one-output Boolean function,Information Processing Letters,18 (1984), 201–202. · Zbl 0548.94040
[17] L. G. Valiant, Completeness classes in algebra,Proceedings of 11 th ACM Symposium on Theory of Computing, (1979), 249–261.
[18] I. Wegener, Boolean functions whose monotone complexity is of sizen 2/logn, Theoretical Computer Science,21 (1982), 213–224. · Zbl 0488.94035
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.