СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ
SIBIRSKII MATEMATICHESKII ZHURNAL


Том 47 (2006), Номер 2, с. 352-360

Когабаев Н. Т.
Сложность некоторых естественных проблем на классе вычислимых I-алгебр

Изучаются вычислимые булевы алгебры с выделенными идеалами (кратко I-алгебры). Доказано, что проблема изоморфизма вычислимых I-алгебр является Σ11-полной. Показано, что проблема вычислимого изоморфизма и проблема вычислимой категоричности вычислимых I-алгебр являются Σ03-полными.

Kogabaev N. T.
Complexity of some natural problems on the class of computable I-algebras

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ11-complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ03-complete.

Полный текст статьи / Full texts:

Адрес редакции:
пр. Коптюга, 4,
Новосибирск 630090.
Телефон: (383-2) 333-493
E-mail: