To prove that P ≠ 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).

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings
EditorsVladimir V. Podolskii, Fedor V. Fomin
PublisherSpringer Nature
Pages15-22
Number of pages8
ISBN (Print)9783319905297
DOIs
StatePublished - 1 Jan 2018
Event13th International Computer Science Symposium in Russia, CSR 2018 - Moscow, Russian Federation
Duration: 6 Jun 201810 Jun 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10846 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Computer Science Symposium in Russia, CSR 2018
Country/TerritoryRussian Federation
CityMoscow
Period6/06/1810/06/18

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 49820627