Отправить статью по E-mail Логический язык описания полиномиальной вычислимости
- Авторы: Гончаров С.С.1, Свириденко Д.И.1
-
Учреждения:
- Институт математики им. С. Л. Соболева Сибирского отделения Российской Академии наук
- Выпуск: Том 485, № 1 (2019)
- Страницы: 11-14
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/12802
- DOI: https://doi.org/10.31857/S0869-5652485111-14
- ID: 12802
Цитировать
Полный текст
Аннотация
Построено расширение понятия терма и соответственно формулы за счёт новых конструкций. Построены расширения языка, сохраняющие выразительность на S-формулах, а на уровне D0-формул и термов, обеспечивающих полиномиальность алгоритмов вычислений значений терма и истинности D0-формулы.
Об авторах
С. С. Гончаров
Институт математики им. С. Л. Соболева Сибирского отделения Российской Академии наук
Автор, ответственный за переписку.
Email: s.s.goncharov@math.nsc.ru
Академик Ран
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4Д. И. Свириденко
Институт математики им. С. Л. Соболева Сибирского отделения Российской Академии наук
Email: dsviridenko47@gmail.com
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4
Список литературы
- Гончаров С.С., Свириденко Д.И. // Вычисл. системы.1985. В. 107. С. 3–29.
- Goncharov S.S., Sviridenko D.I. // Lect. Notes in Com- put. Sci. 1986. V. 215. P. 169–179.
- Ershov Yu.L., Goncharov S.S., Sviridenko D.I. Inform. proces., Proc. IFIP 10-th World Comput. Congr. Dub- lin, 1986. V. 10. P. 1113–1120.
- Гончаров С.С., Свириденко Д.И. // ДАН. 1986. Т. 289. № 6. С. 1324–1328.
- Ershov Yu.L., Goncharov S.S., Sviridenko D.I. // Lect.Notes in Comput. Sci. 1987. V. 278. P. 116–122.
- Ершов Ю. Л. // ДАН. 1983. Т. 270. № 4. С. 786–788.
- Ершов Ю. Л. // ДАН. 1983. Т. 273. № 5. С. 1045–1048.
- Ershov Yu.L. Definability and Computability. Siberian School of Algebra and Logic. N.Y.: Consultants Bureau, 1996. 264 p.
- Barwise J. Admissible Sets and Structures. Berlin: Springer, 1975. 394 p.
- Arora S., Barak B. Computational Complexity. A Mod- ern Approach. Cambridge: Cambridge Univ. Press, 2009. 605 p.
- Papadimitriou Ch. Computational Complexity. Reding: Addison-Wesley, 1994. 523 p.
- Ospichev S. S., Ponomarev D. // Siberian Electronic Math. Reps. 2018. V. 15. P. 987–995.
- Гончаров С.С. // Сиб. мат. журн. 2017. Т. 58. № 5. С. 1026–1034.
Дополнительные файлы
