Является ли проблема конечного обратного полугруппового изоморфизма GI-полной?

11

Является ли проблема конечного обратного полугруппового изоморфизма GI-полной ? Здесь конечные обратные полугруппы предполагаются заданными их таблицами умножения.

cc.complexity-theory graph-isomorphism Томас Климпел
источник
Есть ли конкретная причина для рассмотрения обратных полугрупп? Что известно о сложности проблемы изоморфизма конечных групп и проблемы изоморфизма конечных полугрупп?
Ж.-Е.
1
@ J.-E.Pin Проблема изоморфизма конечных полугрупп является GI-полной, проблема изоморфизма конечных групп неизвестна как GI-полная. Статья в Википедии, связанная с этим вопросом, утверждает, что изоморфизм «нильпотентных коммутативных классов 3 (т. Е. для каждого элемента x , y , z ) полугрупп» является GI-полным. ИксYZзнак равно0Икс,Y,Z
Томас Климпел
1
Коммутативные нильпотентные полугруппы класса 3 не вкладываются в обратные полугруппы, согласно старому результату Б. Шейна, который цитирует здесь Марк Сапир . (Я немного читал в цитируемой статье, но пока не проработал ее полностью «пока», может быть, мне следует.)
Томас Климпел

Ответы:

9

Да, проблема конечного обратного полугруппового изоморфизма является GI-полной! Это следствие

Теорема: решеточный изоморфизм полон изоморфизма

из раздела 7.2 Решетки и Posets в

Бут, Kellogg S .; Colbourn, CJ (1977), Задачи, полиномиально эквивалентные изоморфизму графов, Технический отчет CS-77-04, Департамент компьютерных наук, Университет Ватерлоо.

потому что (полу) решетка также является (идемпотентной коммутативной) обратной полугруппой.

Доказательство теоремы из технического отчета:

граммNм'0''1''1''0'грамм

Идея этого ответа пришла из дискуссии с vzn о достаточно сфокусированных вопросах . Мотивация тратить время на изоморфизм графов также проистекает из неоднократных побуждений ВЗН. J.-E. Пин спросил в комментарии, есть ли какие-то конкретные причины для рассмотрения обратных полугрупп. Идея состояла в том, чтобы иметь структуру, слегка обобщающую группы, которая является GI полной. Я хотел лучше понять связь между групповым изоморфизмом и графовым изоморфизмом, но боюсь, что этот ответ не дает какой-либо информации такого рода.

Томас Климпел
источник
2
Несколько странно, что существует также проблема решетчатого изоморфизма, которая GI-сложная, но неизвестно, что она GI-полная: www2.mta.ac.il/~ishayhav/papers/latticeiso.pdf
Гек Беннетт
1
@HuckBennett Вы действительно смущены, или вы просто хотели бы услышать мое мнение о теории решеток? Название «решетка» просто не повезло : «Г. Биркгоф также ввел английское слово« решетка », которое не является переводом его немецкого эквивалента, но было вдохновлено изображением некоторых диаграмм Хассе, представляющих решетки». Плохой репутации теории решеток можно было бы избежать, разделив ее на алгебраическую логику, анализ формальных понятий и теорию порядка.
Томас Климпел
1
"Вы действительно смущены, или вы просто хотели бы услышать мое мнение по теории решеток?" Ни на самом деле. Я думал, что кто-то в дополнение ко мне, возможно, знаком с этим определением изоморфизма решетки, а не с этим, и что эта связь может помочь.
Гек Беннетт