Математическая энциклопедия

Изоморфизма Проблема

Задача отыскания алгоритма, позволяющего по любой паре эффективно заданных алгебраических систем из данного класса установить, изоморфны они или нет. Частная И. п. для фиксированной алгебраич. системы Асостоит в отыскании алгоритма, распознающего по эффективному заданию алгебраич. системы из рассматриваемого класса, изоморфна она системе Аили нет. Положительное решение (частной) И. п. состоит в указании искомого алгоритма (И. п. разрешима), отрицательное — в доказательстве того, что искомого алгоритма нет (И. п. неразрешима). Обычно И. п. ставится для алгебр, задаваемых образующими и определяющими соотношениями. Для многих важных классов алгебр И. п. неразрешима. Доказана неразрешимость частной И. п. для произвольной конечно определенной полугруппы в классе всех конечно определенных полугрупп [2] и частной И. п. для произвольной конечно определенной группы в классе всех конечно определенных групп [1]. В классе всех групп из многообразия n-ступенно разрешимых групп, задаваемых в этом многообразии конечным числом образующих и определяющих соотношений, при И. п. также неразрешима [3]. И. п. разрешима в классе всех конечных конечно определенных алгебр фиксированной сигнатуры, в классе абелевых групп. Открытыми остаются пока (к 1978) И. п. для нильпотентных групп ступени 2, групп с одним определяющим соотношением. И. п. для групп связана с алгоритмич. проблемами топологии. Лит.:[1] Адян С. И., "Тр. Моск. матем. об-ва", 1957, т. 6, с. 231-98; [2] Марков А. А., Теория алгорифмов, М.-Л., 1954 (Тр. матем. ин-та АН СССР, т. 42); [3] Киркинский А. С, Ремесленников В. Н., "Матем. заметки", 1975, т. 18, № 3, с. 437 — 43. А. Л. Семенов.



ScanWordBase.ru — ответы на сканворды
в Одноклассниках, Мой мир, ВКонтакте