RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Изв. РАН. Сер. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Изв. РАН. Сер. матем., 1995, том 59, выпуск 1, страницы 201–224 (Mi izv9)  

Эта публикация цитируется в 12 научных статьях (всего в 12 статьях)

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.

Полный текст: PDF файл (4581 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Izvestiya: Mathematics, 1995, 59:1, 205–227

Реферативные базы данных:

Тип публикации: Статья
MSC: 03C62
Поступило в редакцию: 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

Цитирование в формате AMSBIB
\RBibitem{Raz95}
\by A.~A.~Razborov
\paper Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
\jour Изв. РАН. Сер. матем.
\yr 1995
\vol 59
\issue 1
\pages 201--224
\mathnet{http://mi.mathnet.ru/izv9}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1328561}
\zmath{https://zbmath.org/?q=an:0838.03045}
\transl
\jour Izv. Math.
\yr 1995
\vol 59
\issue 1
\pages 205--227
\crossref{https://doi.org/10.1070/IM1995v059n01ABEH000009}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1995RZ88700009}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/izv9
  • http://mi.mathnet.ru/rus/izv/v59/i1/p201

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Pudlak P., “Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations”, J. Symb. Log., 62:3 (1997), 981–998  crossref  mathscinet  zmath  isi
    2. Razborov A., “Lower Bounds for the Polynomial Calculus”, Comput. Complex., 7:4 (1998), 291–324  crossref  mathscinet  zmath  isi
    3. Atserias A., Bonet M., “On the Automatizability of Resolution and Related Propositional Proof Systems”, Computer Science Logic, Proceedings, Lecture Notes in Computer Science, 2471, ed. Bradfield J., Springer-Verlag Berlin, 2002, 569–583  crossref  mathscinet  zmath  isi
    4. Albert Atserias, Marı́a Luisa Bonet, “On the automatizability of resolution and related propositional proof systems”, Information and Computation, 189:2 (2004), 182  crossref
    5. Bonet M., Domingo C., Gavalda R., Maciel A., Pitassi T., “Non-Automatizability of Bounded-Depth Frege Proofs”, Comput. Complex., 13:1-2 (2004), 47–68  crossref  mathscinet  zmath  isi
    6. Allender E., “Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds”, Computer Science - Theory and Applications, Lecture Notes in Computer Science, 5010, eds. Hirsch E., Razborov A., Semenov A., Slissenko A., Springer-Verlag Berlin, 2008, 3–10  crossref  zmath  isi
    7. Pudlak P., “Twelve Problems in Proof Complexity”, Computer Science - Theory and Applications, Lecture Notes in Computer Science, 5010, eds. Hirsch E., Razborov A., Semenov A., Slissenko A., Springer-Verlag Berlin, 2008, 13–27  crossref  mathscinet  zmath  isi
    8. Allender E., Koucky M., “Amplifying Lower Bounds by Means of Self-Reducibility”, Twenty-Third Annual IEEE Conference on Computational Complexity, Proceedings, Annual IEEE Conference on Computational Complexity, IEEE Computer Soc, 2008, 31–40  crossref  mathscinet  isi
    9. Krajicek J., “A Form of Feasible Interpolation for Constant Depth Frege Systems”, J. Symb. Log., 75:2 (2010), 774–784  crossref  mathscinet  zmath  isi
    10. Allender E., Kouckuy M., “Amplifying Lower Bounds by Means of Self-Reducibility”, J. ACM, 57:3 (2010), 14  crossref  mathscinet  isi
    11. Alexander Razborov, “Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution”, Ann. Math, 181:2 (2015), 415  crossref
    12. J.A.. Grochow, “Unifying Known Lower Bounds via Geometric Complexity Theory”, comput. complex, 2015  crossref
  • Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Просмотров:
    Эта страница:249
    Полный текст:73
    Литература:26
    Первая стр.:3

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018