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

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

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



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






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


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

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

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

Удмуртский государственный университет

Аннотация: Строится семейство слабых конструктивных теорий, содержащих арифметику и теорию функций натуральных аргументов с натуральными значениями. Функции, являющиеся значениями функциональных переменных, должны удовлетворять следующим условиям: во-первых, каждая такая функция вычислима за время, ограниченное некоторым полиномом от ее аргументов; во-вторых, каждое значение такой функции ограничено некоторым полиномом от соответствующих значений аргументов. Языки теорий содержат функциональные константы для сложения и умножения натуральных чисел и предикатную константу для равенства натуральных чисел. Допустимо и наличие других функциональных и предикатных констант. Требуется, чтобы функции, обозначаемые этими функциональными константами, удовлетворяли вышеупомянутым условиям полиномиальной ограниченности. Из доказательств рассматриваемых теорий алгоритмически извлекаются реализации доказываемых формул с алгоритмами полиномиальной временной сложности (от значений числовых аргументов этих алгоритмов). Если одним из аргументов реализации должна быть функция, то в реализующем алгоритме эта функция используется как оракул. Библ. – 2 назв.

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

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

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

УДК: 517.11
Поступило: 30.11.2002

Образец цитирования: А. П. Бельтюков, “Слабая конструктивная арифметика второго порядка с извлечением алгоритмов, вычислимых за полиномиальное время”, Теория сложности вычислений. 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://www.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}


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

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