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

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

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



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






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


Известия Российской академии наук. Серия математическая, 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
Англоязычная версия:
Izvestiya: Mathematics, 1995, Volume 59, Issue 1, Pages 205–227
DOI: https://doi.org/10.1070/IM1995v059n01ABEH000009
Реферативные базы данных:
Тип публикации: Статья
MSC: 03C62
Язык публикации: английский
Образец цитирования: 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/im9}
\mathscinet{http://mathscinet.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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=A1995RZ88700009}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/im9
  • https://www.mathnet.ru/rus/im/v59/i1/p201
  • Эта публикация цитируется в следующих 34 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Статистика просмотров:
    Страница аннотации:466
    PDF русской версии:149
    PDF английской версии:41
    Список литературы:56
    Первая страница:3
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024