DOI

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).

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings
РедакторыVladimir V. Podolskii, Fedor V. Fomin
ИздательSpringer Nature
Страницы15-22
Число страниц8
ISBN (печатное издание)9783319905297
DOI
СостояниеОпубликовано - 1 янв 2018
Событие13th International Computer Science Symposium in Russia, CSR 2018 - Moscow, Российская Федерация
Продолжительность: 6 июн 201810 июн 2018

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том10846 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция13th International Computer Science Symposium in Russia, CSR 2018
Страна/TерриторияРоссийская Федерация
ГородMoscow
Период6/06/1810/06/18

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49820627