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

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

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



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






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


Записки научных семинаров ПОМИ, 2003, том 304, страницы 7–12 (Mi znsl875)  

Слабая конструктивная арифметика второго порядка с извлечением алгоритмов, вычислимых за полиномиальное время

А. П. Бельтюков

Удмуртский государственный университет
Список литературы:
Аннотация: Строится семейство слабых конструктивных теорий, содержащих арифметику и теорию функций натуральных аргументов с натуральными значениями. Функции, являющиеся значениями функциональных переменных, должны удовлетворять следующим условиям: во-первых, каждая такая функция вычислима за время, ограниченное некоторым полиномом от ее аргументов; во-вторых, каждое значение такой функции ограничено некоторым полиномом от соответствующих значений аргументов. Языки теорий содержат функциональные константы для сложения и умножения натуральных чисел и предикатную константу для равенства натуральных чисел. Допустимо и наличие других функциональных и предикатных констант. Требуется, чтобы функции, обозначаемые этими функциональными константами, удовлетворяли вышеупомянутым условиям полиномиальной ограниченности. Из доказательств рассматриваемых теорий алгоритмически извлекаются реализации доказываемых формул с алгоритмами полиномиальной временной сложности (от значений числовых аргументов этих алгоритмов). Если одним из аргументов реализации должна быть функция, то в реализующем алгоритме эта функция используется как оракул. Библ. – 2 назв.
Поступило: 30.11.2002
Англоязычная версия:
Journal of Mathematical Sciences (New York), 2005, Volume 130, Issue 2, Pages 4571–4573
DOI: https://doi.org/10.1007/s10958-005-0351-4
Реферативные базы данных:
УДК: 517.11
Образец цитирования: А. П. Бельтюков, “Слабая конструктивная арифметика второго порядка с извлечением алгоритмов, вычислимых за полиномиальное время”, Теория сложности вычислений. VIII, Зап. научн. сем. ПОМИ, 304, ПОМИ, СПб., 2003, 7–12; J. Math. Sci. (N. Y.), 130:2 (2005), 4571–4573
Цитирование в формате AMSBIB
\RBibitem{Bel03}
\by А.~П.~Бельтюков
\paper Слабая конструктивная арифметика второго порядка с~извлечением алгоритмов, вычислимых за полиномиальное время
\inbook Теория сложности вычислений.~VIII
\serial Зап. научн. сем. ПОМИ
\yr 2003
\vol 304
\pages 7--12
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl875}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2054746}
\zmath{https://zbmath.org/?q=an:1145.03338}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2005
\vol 130
\issue 2
\pages 4571--4573
\crossref{https://doi.org/10.1007/s10958-005-0351-4}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/znsl875
  • https://www.mathnet.ru/rus/znsl/v304/p7
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Статистика просмотров:
    Страница аннотации:320
    PDF полного текста:86
    Список литературы:55
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024