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

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

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



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






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


Зап. научн. сем. ПОМИ, 2003, том 304, страницы 99–120 (Mi znsl879)  

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

$S_{k,\exp}$ does not prove $\mathrm{NP}=\mathrm{co}-\mathrm{NP}$ uniformly

[$S_{k,\exp}$ не доказывает $\mathrm{NP}=\mathrm{co}-\mathrm{NP}$ равномерно]

Ch. Pollett

Department of Computer Science San Jose State University

Аннотация: Вводится понятие равномерного доказательства в исчислении секвенций. Затем показывается, что в $S_{k,\exp}$ (условии хорошо изученной системы $S_k$, ограниченной арифметики Басса) не существует равномерного доказательства $\mathrm{NP}=\mathrm{co}=\mathrm{NP}$. Получен также немного более сильный результат: в $S_{k,\exp}$ не существует равномерного доказательства $\widehat\Sigma^b_{1,k'}=\widehat\Pi_{1,k'}^b$ для $2\le k'\le k$. Затем, применяя вариант того же метода, показывается, что $S_{k,\exp}$ не доказывает теорему Дэвиса–Патнама–Робинсона–Матиясевича. В этом результате условие равномерности не упоминается. Затем представлено обобщение обоих результатов на более высокие уровни иерархии Гжегорчика. Библ. – 21 назв.

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

Англоязычная версия:
Journal of Mathematical Sciences (New York), 2005, 130:2, 4607–4619

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

УДК: 517.11
Поступило: 03.05.2003
Язык публикации: английский

Образец цитирования: Ch. Pollett, “$S_{k,\exp}$ does not prove $\mathrm{NP}=\mathrm{co}-\mathrm{NP}$ uniformly”, Теория сложности вычислений. VIII, Зап. научн. сем. ПОМИ, 304, ПОМИ, СПб., 2003, 99–120; J. Math. Sci. (N. Y.), 130:2 (2005), 4607–4619

Цитирование в формате AMSBIB
\RBibitem{Pol03}
\by Ch.~Pollett
\paper $S_{k,\exp}$ does not prove $\mathrm{NP}=\mathrm{co}-\mathrm{NP}$ uniformly
\inbook Теория сложности вычислений.~VIII
\serial Зап. научн. сем. ПОМИ
\yr 2003
\vol 304
\pages 99--120
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl879}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2054750}
\zmath{https://zbmath.org/?q=an:1145.03337}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2005
\vol 130
\issue 2
\pages 4607--4619
\crossref{https://doi.org/10.1007/s10958-005-0355-0}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/znsl879
  • http://mi.mathnet.ru/rus/znsl/v304/p99

    ОТПРАВИТЬ: 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. Pollet C., “A Theory for Log-Space and Nlin Versus Co-Nlin”, J. Symb. Log., 68:4 (2003), 1082–1090  crossref  mathscinet  zmath  isi  scopus
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:120
    Полный текст:25
    Литература:28
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020