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

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

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 Σ^1₁-complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ^0₃-complete.

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

• PDF file (465 KB)
• PostScript file (905 KB)