|
Сибирский математический журнал, 2006, том 47, номер 2, страницы 352–360
(Mi smj860)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Сложность некоторых естественных проблем на классе вычислимых $I$-алгебр
Н. Т. Когабаев Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Изучаются вычислимые булевы алгебры с выделенными идеалами (кратко $I$-алгебры). Доказано, что проблема изоморфизма вычислимых $I$-алгебр является $\sigma_1^1$-полной. Показано, что проблема вычислимого изоморфизма и проблема вычислимой категоричности вычислимых $I$-алгебр являются $\Sigma_3^0$-полными.
Ключевые слова:
вычислимая булева алгебра с выделенными идеалами, вычислимый изоморфизм, вычислимо категоричная структура, арифметическая сложность, аналитическая сложность.
Статья поступила: 01.02.2005
Образец цитирования:
Н. Т. Когабаев, “Сложность некоторых естественных проблем на классе вычислимых $I$-алгебр”, Сиб. матем. журн., 47:2 (2006), 352–360; Siberian Math. J., 47:2 (2006), 291–297
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj860 https://www.mathnet.ru/rus/smj/v47/i2/p352
|
Статистика просмотров: |
Страница аннотации: | 321 | PDF полного текста: | 85 | Список литературы: | 59 |
|