Skip to main content
Top

2018 | OriginalPaper | Chapter

Lower Bounds for Unrestricted Boolean Circuits: Open Problems

Author : Alexander S. Kulikov

Published in: Computer Science – Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

To prove that \(\text {P} \ne \text {NP}\), it suffices to prove a superpolynomial lower bound on Boolean circuit complexity of a function from NP. Currently, we are not even close to achieving this goal: we do not know how to prove a 4n lower bound. What is more depressing is that there are almost no techniques for proving circuit lower bounds.
In this note, we briefly review various approaches that could potentially lead to stronger linear or superlinear lower bounds for unrestricted Boolean circuits (i.e., circuits with no restriction on depth, fan-out, or basis).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
2.
go back to reference Find, M.G., Golovnev, A., Hirsch, E.A., Kulikov, A.S.: A better-than-3n lower bound for the circuit complexity of an explicit function. In: Dinur, I. (ed.) IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, NJ, USA, 9–11 October 2016, pp. 89–98. IEEE Computer Society (2016) Find, M.G., Golovnev, A., Hirsch, E.A., Kulikov, A.S.: A better-than-3n lower bound for the circuit complexity of an explicit function. In: Dinur, I. (ed.) IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, NJ, USA, 9–11 October 2016, pp. 89–98. IEEE Computer Society (2016)
3.
go back to reference Golovnev, A., Hirsch, E.A., Knop, A., Kulikov, A.S.: On the limits of gate elimination. [27], pp. 46:1–46:13 Golovnev, A., Hirsch, E.A., Knop, A., Kulikov, A.S.: On the limits of gate elimination. [27], pp. 46:1–46:13
4.
go back to reference Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner, Hoboken (1987)MATH Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner, Hoboken (1987)MATH
5.
go back to reference Lamagna, E.A., Savage, J.E.: On the logical complexity of symmetric switching functions in monotone and complete bases. Technical report, Brown University (1973) Lamagna, E.A., Savage, J.E.: On the logical complexity of symmetric switching functions in monotone and complete bases. Technical report, Brown University (1973)
6.
go back to reference Hiltgen, A.P.: Cryptographically relevant contributions to combinational complexity theory. Ph.D. thesis, ETH Zurich, Zürich, Switzerland (1994) Hiltgen, A.P.: Cryptographically relevant contributions to combinational complexity theory. Ph.D. thesis, ETH Zurich, Zürich, Switzerland (1994)
7.
go back to reference Blum, N., Seysen, M.: Characterization of all optimal networks for a simultaneous computation of AND and NOR. Acta Inf. 21, 171–181 (1984)MathSciNetCrossRefMATH Blum, N., Seysen, M.: Characterization of all optimal networks for a simultaneous computation of AND and NOR. Acta Inf. 21, 171–181 (1984)MathSciNetCrossRefMATH
8.
9.
go back to reference Chashkin, A.V.: On complexity of Boolean matrices, graphs and corresponding Boolean matrices. Diskretnaya matematika 6(2), 43–73 (1994). (in Russian)MATH Chashkin, A.V.: On complexity of Boolean matrices, graphs and corresponding Boolean matrices. Diskretnaya matematika 6(2), 43–73 (1994). (in Russian)MATH
10.
go back to reference Demenkov, E., Kojevnikov, A., Kulikov, A.S., Yaroslavtsev, G.: New upper bounds on the Boolean circuit complexity of symmetric functions. Inf. Process. Lett. 110(7), 264–267 (2010)MathSciNetCrossRefMATH Demenkov, E., Kojevnikov, A., Kulikov, A.S., Yaroslavtsev, G.: New upper bounds on the Boolean circuit complexity of symmetric functions. Inf. Process. Lett. 110(7), 264–267 (2010)MathSciNetCrossRefMATH
11.
12.
14.
go back to reference Golovnev, A., Kulikov, A.S., Smal, A.V., Tamaki, S.: Circuit size lower bounds and #SAT upper bounds through a general framework. [27], pp. 45:1–45:16 Golovnev, A., Kulikov, A.S., Smal, A.V., Tamaki, S.: Circuit size lower bounds and #SAT upper bounds through a general framework. [27], pp. 45:1–45:16
15.
go back to reference Williams, R.R.: Some ways of thinking algorithmically about impossibility. SIGLOG News 4(3), 28–40 (2017) Williams, R.R.: Some ways of thinking algorithmically about impossibility. SIGLOG News 4(3), 28–40 (2017)
16.
17.
go back to reference Ulig, D.: On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements. Math. Notes Acad. Sci. USSR 15(6), 558–562 (1974)MathSciNet Ulig, D.: On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements. Math. Notes Acad. Sci. USSR 15(6), 558–562 (1974)MathSciNet
18.
go back to reference Valiant, L.G.: Exponential lower bounds for restricted monotone circuits. In: Johnson, D.S., Fagin, R., Fredman, M.L., Harel, D., Karp, R.M., Lynch, N.A., Papadimitriou, C.H., Rivest, R.L., Ruzzo, W.L., Seiferas, J.I. (eds.) Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, USA, 25–27 April 1983, pp. 110–117. ACM (1983) Valiant, L.G.: Exponential lower bounds for restricted monotone circuits. In: Johnson, D.S., Fagin, R., Fredman, M.L., Harel, D., Karp, R.M., Lynch, N.A., Papadimitriou, C.H., Rivest, R.L., Ruzzo, W.L., Seiferas, J.I. (eds.) Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, USA, 25–27 April 1983, pp. 110–117. ACM (1983)
20.
go back to reference Lupanov, O.B.: On rectifier and switching-and-rectifier schemes. Dokl. Akad. Nauk SSSR 111, 1171–1174 (1956)MathSciNetMATH Lupanov, O.B.: On rectifier and switching-and-rectifier schemes. Dokl. Akad. Nauk SSSR 111, 1171–1174 (1956)MathSciNetMATH
21.
go back to reference Grigoriev, D.: An application of separability and independence notions for proving lower bounds of circuit complexity. Notes Sci. Semin. LOMI 60, 38–48 (1976) Grigoriev, D.: An application of separability and independence notions for proving lower bounds of circuit complexity. Notes Sci. Semin. LOMI 60, 38–48 (1976)
25.
go back to reference Nechiporuk, E.I.: Complexity of schemes in certain bases containing nontrivial elements with zero weights. Dokl. Akad. Nauk SSSR 139(6), 1302–1303 (1961)MATH Nechiporuk, E.I.: Complexity of schemes in certain bases containing nontrivial elements with zero weights. Dokl. Akad. Nauk SSSR 139(6), 1302–1303 (1961)MATH
27.
go back to reference Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.): 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. LIPIcs, vol. 58, Kraków, Poland, 22–26 August 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016) Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.): 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. LIPIcs, vol. 58, Kraków, Poland, 22–26 August 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)
Metadata
Title
Lower Bounds for Unrestricted Boolean Circuits: Open Problems
Author
Alexander S. Kulikov
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-90530-3_2

Premium Partner