|
Эта публикация цитируется в 34 научных статьях (всего в 34 статьях)
Структуры, вычислимые за полиномиальное время. I
П. Е. Алаевab a Ин-т матем. им. С. Л. Соболева СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ
b Новосибирский гос. ун-т, ул. Пирогова, 2, г. Новосибирск, 630090, РОССИЯ
Аннотация:
Доказывается, что любая вычислимая локально конечная структура с конечным числом функций обладает представлением, вычислимым за полиномиальное время. Кроме того, структура, вычислимая за полиномиальное время, является полиномиально категоричной тогда и только тогда, когда она конечна. Если структура вычислима за полиномиальное время и локально конечна, то она слабо полиномиально категорична (т.е. категорична относительно примитивно рекурсивных изоморфизмов) тогда
и только тогда, когда конечна.
Ключевые слова:
локально конечная структура, вычислимая структура, структура, вычислимая за полиномиальное время, полиномиально категоричная структура, слабо полиномиально категоричная структура.
Поступило: 09.11.2015 Окончательный вариант: 07.12.2015
Образец цитирования:
П. Е. Алаев, “Структуры, вычислимые за полиномиальное время. I”, Алгебра и логика, 55:6 (2016), 647–669; Algebra and Logic, 55:6 (2017), 421–435
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al769 https://www.mathnet.ru/rus/al/v55/i6/p647
|
Статистика просмотров: |
Страница аннотации: | 375 | PDF полного текста: | 177 | Список литературы: | 60 | Первая страница: | 19 |
|