Czy skończony odwrotny problem izomorfizmu półgrupy GI jest kompletny?

11

Czy skończony odwrotny problem izomorfizmu półgrupy GI jest kompletny ? Tutaj zakłada się, że skończone odwrotne półgrupy są podane przez ich tabliczki mnożenia.

cc.complexity-theory graph-isomorphism Thomas Klimpel
źródło
Czy jest jakiś konkretny powód, aby rozważyć odwrotne półgrupy? Co wiadomo na temat złożoności problemu izomorfizmu skończonej grupy i problemu izomorfizmu skończonej półgrupy?
J.-E.
1
@ J.-E.Pin Problem z izomorfizmem skończonych półgrup jest zakończony GI, problem z izomorfizmem skończonych grup nie jest znany z GI. Artykuł w Wikipedii, do którego link znajduje się w pytaniu, stwierdza, że ​​izomorfizm „przemiennej klasy nilpotent 3 (tj. dla każdego elementu ) półgrupy” jest kompletny. x , y , zxyz=0x,y,z
Thomas Klimpel
1
Przemienne klasa 3 nilpotent półgrupy nie jest zabudowany w odwrotnych półgrup, według starej wyniku B. Schein, cytowanego przez Marka Sapira tutaj . (Przeczytałem trochę w cytowanym artykule, ale nie przeszedłem dogłębnie „jeszcze”, może powinienem.)
Thomas Klimpel

Odpowiedzi:

9

Tak, skończony odwrotny problem izomorfizmu półgrup jest zakończony GI! Jest to następstwo

Twierdzenie: Izomorfizm kratowy jest zakończony izomorfizmem

z sekcji 7.2 Kraty i pozy w

Booth, Kellogg S .; Colbourn, CJ (1977), Problemy wielomianowo równoważne z izomorfizmem grafów, Raport techniczny CS-77-04, Wydział Informatyki, University of Waterloo.

ponieważ (pół) sieć jest również odwrotną półgrupą (idempotentną komutatywną).

Dowód twierdzenia z raportu technicznego:

Wystarczy przedstawić wykres jednoznacznie jako sieć. Biorąc pod uwagę wykres z n wierzchołkami i krawędziami m , definiujemy sieć z elementem dla każdego wierzchołka, elementem dla każdej krawędzi oraz dwoma dodatkowymi elementami „ 0 ” i „ 1 ” . Element „ 1 ” dominuje nad wszystkimi innymi ( supremum ), a element „ 0 ” jest zdominowany przez wszystkie inne elementy ( infimum ). Krawędź dominuje dokładnie te wierzchołki, które są jej punktami końcowymi. Rezultatem jest kratownica, która jednoznacznie oznacza G .solnm„0„„1„„1„„0„sol

Pomysł na tę odpowiedź zrodził się z dyskusji z vzn na temat wystarczająco ukierunkowanych pytań . Motywacja do spędzania czasu na izomorfizmie grafów w ogóle wynikała również z wielokrotnego szturchania Vzn. J.-E. Pin zapytał w komentarzu, czy istnieją jakieś szczególne powody, aby rozważyć odwrotne półgrupy. Chodziło o to, aby mieć strukturę nieco uogólniającą grupy, która jest kompletna. Chciałem lepiej zrozumieć związek między izomorfizmem grupowym a izomorfizmem grafowym, ale obawiam się, że ta odpowiedź nie daje żadnego takiego wglądu.

Thomas Klimpel
źródło
2
Nieco mylące jest także to, że występuje problem z izomorfizmem sieci, który jest trudny do oznaczenia, ale nie jest znany jako kompletny: www2.mta.ac.il/~ishayhav/papers/latticeiso.pdf
Huck Bennett
1
@HuckBennett Czy jesteś naprawdę zdezorientowany, czy po prostu chciałbyś usłyszeć moją opinię na temat teorii sieci? Nazwa „krata” jest po prostu pechowa : „G. Birkhoff wprowadził także angielskie słowo„ krata ”, które nie jest tłumaczeniem jej niemieckiego odpowiednika, ale zostało zainspirowane obrazem niektórych diagramów Hassego przedstawiających kraty”. Złą reputację teorii sieci można było uniknąć, dzieląc ją na logikę algebraiczną, formalną analizę pojęć i teorię porządku.
Thomas Klimpel
1
„Czy jesteś naprawdę zdezorientowany, czy chciałbyś po prostu usłyszeć moją opinię na temat teorii sieci?” Tak naprawdę nie. Myślałem, że ktoś oprócz mnie mógł znać tę definicję izomorfizmu sieci, a nie tę, i że link może pomóc.
Huck Bennett