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

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

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



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






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


Зап. научн. сем. ПОМИ, 2012, том 399, страницы 109–127 (Mi znsl5223)  

Диофантова иерархия

А. А. Кноп

Санкт-Петербургский государственный университет, Санкт-Петербург, Россия

Аннотация: Класс языков $\mathrm D$, определённый в работе L. Adelman и K. Manders (1975), является диофантовым аналогом класса $\mathrm{NP}$. Язык $\mathrm L$ принадлежит классу $\mathrm D$ тогда и тогда, когда существует многочлен $P$, такой, что $x$ принадлежит $\mathrm L$, если и только если существуют числа $y_i$ полиномиальной длины, такие, что $P(x,y_1,…,y_m)=0$.
Вопрос о равенстве классов $\mathrm D$ и $\mathrm{NP}$ открыт. В работе определяется иерархия на основе класса $\mathrm D$, аналогичная традиционной полиномиальной иерархии (на основе класса $\mathrm{NP}$) и доказывается связь между двумя иерархиями (в частности, $\mathrm{NP}$ содержится во втором уровне диофантовой иерархии). Библ. – 6 назв.

Ключевые слова: диофантова сложность.

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

Англоязычная версия:
Journal of Mathematical Sciences (New York), 2013, 188:1, 59–69

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

Тип публикации: Статья
УДК: 510.52+519.6
Поступило: 12.04.2012

Образец цитирования: А. А. Кноп, “Диофантова иерархия”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 109–127; J. Math. Sci. (N. Y.), 188:1 (2013), 59–69

Цитирование в формате AMSBIB
\RBibitem{Kno12}
\by А.~А.~Кноп
\paper Диофантова иерархия
\inbook Теория сложности вычислений.~X
\serial Зап. научн. сем. ПОМИ
\yr 2012
\vol 399
\pages 109--127
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl5223}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2945002}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2013
\vol 188
\issue 1
\pages 59--69
\crossref{https://doi.org/10.1007/s10958-012-1106-7}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84871936998}


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

    ОТПРАВИТЬ: 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
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:173
    Полный текст:62
    Литература:13
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020