Summary
We develop a complexity theory based on the concept of the graph instead of the Boolean function. We show its relation to the Boolean complexity and prove some lower bounds to the complexity of explicitly given graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Babai, L, Frankl, P., Simon, J.: Complexity classes in communication complexity, 27th FOCS, pp 337–347 (1986)
Babai, L., Pudlák, P., Rödl, V., Szemeredi, E.: Lower bounds to the complexity of symmetric Boolean functions. Theor. Comput. Sci. (submitted for publication)
Berge, C.: Graphs and hypergraphs. Amsterdam Oxford New York: North-Holland, American Elsevier 1973
Bublitz, S.: Decomposition of graphs and monotone formula size of homogeneous functions. Acta Informatica 23, 689–696 (1986)
Erdös, P., Spencer, J.: Probabilistic methods in combinatorics. Budapest: Akadémiai Kiadó 1979
Frankl, P., Rödl, V., Wilson, R.M.: The number of submatrices of given type in a Hadamard matrix and related results. J. Comb. Theor B (to appear)
Nečiporuk, E.T.: On a Boolean function. Sov Math Dokl 2, 4, 999–1000 (1966)
Razborov, A.A.: Formuly organičenoj glubiny v bazise {&, ⊕} i nekotorye kombinatornye zadači (Formulas of bounded depth in basis {&, ⊕} and some combinatorial problems), in Složnost' algoritmov i prikladnaja matematičoeskaja logika, S.I. Adjan editor (1987)
Savage, I.E.: The complexity of computing. New York: Wiley 1976
Sgall, J.: Personal communication (1987)
Tuza, Z.: Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices. Combinatorica 4, 111–116 (1984)
Wegener, I.: On the complexity of slice functions. In: Chytil, M.P., Koubek, V. (eds.) Mathematical Foundations of Computer Science. Proceedings, 11th Symposium Praha, Czechoslovakia Sept. 3–7, 1984. (Lect. Notes Comput. Sci., vol. 176, pp. 553–561) Berlin Heidelberg New York: Springer 1984
Wegener, I.: The complexity of Boolean functions. Stuttgart: B.G. Teubner/New York: Wiley 1987
MacWilliams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. Amsterdam New York: North-Holland 1978
Yao, A.C.-C.: Some complexity questions related to distributive computing. Proc. 11th ACM STOC, pp 209–213 (1979)
Author information
Authors and Affiliations
Additional information
The paper was written while the first author was visiting Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago
Rights and permissions
About this article
Cite this article
Pudlák, P., Rödl, V. & Savický, P. Graph complexity. Acta Informatica 25, 515–535 (1988). https://doi.org/10.1007/BF00279952
Received:
Issue date:
DOI: https://doi.org/10.1007/BF00279952