Abstract
We present some criteria for obtaining lower bounds for the formula size of Boolean functions. In the monotone case we get the boundn Ω(logn) for the function “MINIMUM COVER” using methods considerably simpler than all previously known. In the general case we are only able to prove that the criteria yield an exponential lower bound when applied to almost all functions. Some connections with graph complexity and communication complexity are also given.
Similar content being viewed by others
References
A. E. АНДРЕЕВ, ОБ ОДНОМ МЕтОДЕ пОлУЧЕНИь НИжНИх ОцЕНОк слОж НОстИ ИНДИВИДУАльН ых МОНОтОННых ФУНкцИИ — ДАН сссР,1985, т. 282, N5, 1033–1037. (Engl. transl. in:Sov. Math. Dokl. 31, 530–534.)
A. E. АНДРЕЕВ, ОБ ОДНОМ МЕтОДЕ пОлУЧЕНИь ЁФФЕктИВНых НИжНИх ОцЕНОк МОНОтОННОИ слОжНОстИ, АлгЕБРА И лОгИкА,1987, т. 26, 1, с. 3–26.
А. А. РАжБОРОВ, НИжНИЕ ОцЕНкИ МОНОтОННОИ слОжНОстИ НЕкОтОРых БУлЕВых ФУНкцИИ — ДАН сссР,1985, т. 281, N4, с. 798–801. (Engl. transl. in:Sov. Math. Dokl. 31, 354–357.)
А. А. РАжБОРОВ, НИжНИЕ ОцЕНкИ МОНОтОННОИ слОжНОстИ лОгИЧЕс кОгО пЕРМАНЕНтА — “МАтЕМ. жАМ.”,1985, т. 37, Вып. 6, с. 887–900. (Engl. transl. in:Mathem. Notes of the Academy of Sci. of the USSR 37, 485–493.)
А. А. РАжБОРОВ, НИж НИЕ ОцЕНкИ РАжМЕРА сх ЕМ ОгРАНИЧЕННОИ глУБИНы В пОлНОМ БАжИсЕ, сОДЕРжАЩЕМ ФУНкцИУ лОгИЧЕскОгО слОжЕНИь —МАтЕМ. жАМ.,1987, т. 41, Вып. 4, с. 598–607. (Engl. transl. in:Mathem. Notes of the Academy of Sci. of the USSR. 41:4, 333–338.)
А. А.РАжБОРОВ, ФОРМУлы ОгРАНИЧЕННОИ глУБИНы В БАжИсЕ &, ⊕ И НЕкОтОРыЕ кОМБИНАтОРНыЕ жАДАЧИ — В сБ. «ВОпРОсы кИБЕРНЕтИкИ. слОж НОсть ВыЧИслЕНИИ И пРИклАДНАь МАтЕМАтИЧЕскАь лОг ИкА», М.:1988, с. 149–166.
к. л.РыНкОВ, МОДИФИ кАцИь МЕтОДА В. М. хРАпЧЕНкО И пРИМЕНЕНИЕ ЕЕ к ОцЕНк АМ слОжНОстИ п-схЕМ Дль кОДОВых ФУНкцИИ — В сБ. «МЕтОДы ДИскРЕтНОгО АНАлИжА В тЕОРИИ гРАФОВ И схЕМ», Вып. 42, НОВОсИБИРск,1985, с. 91–98.
В. М. хРАпЧЕНкО, О слОжНОстИ РЕАлИжАцИИ лИНЕИНОИ ФУНкцИИ В клАссЕ п-схЕМ,МАтЕМ. жАМ.,1971, т. 9, Вып. 1, с. 35–40. (Engl. transl. in:Mathem. Notes of the Academy of Sci. of the USSR 11 (1972), 474–479.)
A. V.Aho, J. D.Ullman, M.Yannakakis, On Notions of Information Transfer in VLSI Circuits —Proc. 15th ACM STOC,1983, 133–139.
N. Alon, R. B. Boppana, The monotone circuit complexity of Boolean functions,Combinatorica,1987, v. 7, N1, 1–22.
L.Babai, P.Frankl, J.Simon, Complexity classes in communication complexity theory,Proc. 27th IEEE FOCS,1986, 337–347.
A. Borodin, von zur Gathen, J. Hopcroft, Fast parallel matrix and GCD computations,Information and Control,52 (1982), 241–256.
B.Halsenberg, R.Reischuk, On Different Modes of Communication, 1988, 20th ACM STOC. 162–172.
M.Karchmer, A.Wigderson, Monotone Circuits for Connectivity Require Super-logarithmic Depth,Proc. 20th ACM STOC,1988, 539–550.
B. Lindström, H. O. Zetterström, A combinatorial problem in thek-adic number system,Proc. of the Amer. Math. Soc., 1967,18, 1, 166–170.
R. J.Lipton, R.Sedgewick, Lower Bounds for VLSI,Proc. 13th ACM STOC,1981, 300–307.
K.Mehlhorn, E. M.Schmidt, Las Vegas is better than determinism in VLSI and distributive computing,Proc. 14th ACM STOC,1982, 330–337.
P.Pudlak, V.Rödl,A combinatorial approach to complexity—unpublished manuscript,1989.
P. Pudlak, V. Rödl, P. Savicky, Graph Complexity,Acta Informatica,25 (1988), 515–535.
P. M. Spira, On time-hardware complexity tradeoffs for Boolean functions,Proceedings of 4th Hawaii Symposium on System Sciences,1971, Western Periodicals Company, North Hollywood, 525–527.
é. Tardos, The gap between monotone and non-monotone circuit complexity is exponential,Combinatorica,1988, v. 8,1, 141–142.
I. Wegeher, Relating monotone formula size and monotone depth of Boolean functions,Information Processing Letters,16, (1983), 41–42.
A. C.Yao, Some Complexity Questions Related to Distributed Computing,Proc. 11th ACM STOC,1979, 209–213.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Razborov, A.A. Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica 10, 81–93 (1990). https://doi.org/10.1007/BF02122698
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02122698