|
Известия Российской академии наук. Серия математическая, 1995, том 59, выпуск 1, страницы 201–224
(Mi im9)
|
|
|
|
Эта публикация цитируется в 34 научных статьях (всего в 34 статьях)
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
A. A. Razborov Institute for Advanced Study, School of Mathematics
Аннотация:
We show that if strong pseudorandom generators exist then the statement "$\alpha$ encodes a circuit of size $n^{(\log^*n)}$ for SATISFIABILITY" is not refutable in $S_2^2(\alpha)$. For refutation in $S_2^1(\alpha)$, this is proven under the weaker assumption of the existence of generators secure against the attack by small depth circuits, and for another system which is strong enough to prove exponential lower bounds for constant-depth circuits, this is shown without using any unproven hardness assumptions.
These results can be also viewed as direct corollaries of interpolation-like theorems for certain “split versions” of classical systems of Bounded Arithmetic introduced in this paper.
Bibliography: 36 titles.
Поступило в редакцию: 21.04.1994
Образец цитирования:
A. A. Razborov, “Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic”, Изв. РАН. Сер. матем., 59:1 (1995), 201–224; Izv. Math., 59:1 (1995), 205–227
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/im9 https://www.mathnet.ru/rus/im/v59/i1/p201
|
Статистика просмотров: |
Страница аннотации: | 466 | PDF русской версии: | 149 | PDF английской версии: | 41 | Список литературы: | 56 | Первая страница: | 3 |
|