Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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 июн 2018 → 10 июн 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/18 → 10/06/18 |
ID: 49820627