Problém skupinového izomorfismu - Group isomorphism problem

v abstraktní algebra, problém skupinového izomorfismu je rozhodovací problém rozhodování, zda jsou uvedeny dva finální skupinové prezentace současnost, dárek izomorfní skupiny.

Problém isomorfismu byl identifikován pomocí Max Dehn v roce 1911^[1] jako jeden ze tří základních problémů rozhodování v teorii skupin; další dva jsou slovní úloha a problém konjugace. Všechny tři problémy jsou nerozhodnutelný: neexistuje počítačový algoritmus, který by správně řešil každou instanci problému izomorfismu nebo dalších dvou problémů, bez ohledu na to, kolik času je na spuštění algoritmu povoleno. Ve skutečnosti je problém rozhodování, zda je skupina triviální, nerozhodnutelný,^[2] důsledek Adian-Rabinova věta kvůli Sergej Adian a Michael O. Rabin.

Reference

^ Dehn 1911.
^ Miller, Charles (1992). „Problémy s rozhodováním pro skupiny - průzkum a úvahy.“ (PDF). Algoritmy a klasifikace v kombinatorické teorii grup. Algoritmy a klasifikace v kombinatorické teorii grup (Berkeley, CA, 1989). Dodatek 3.4: Springer. s. 1–59.CS1 maint: umístění (odkaz)

Magnus, Wilhelm; Abraham Karrass; Donald Solitar (1976). Teorie kombinatorické grupy. Prezentace skupin z hlediska generátorů a vztahů. Dover Publications. str. 24. ISBN 0-486-63281-4.
Johnson, D.L. (1990). Prezentace skupin. Cambridge University Press. str. 49. ISBN 0-521-37203-8.
Dehn, Max (1911). „Über unendliche diskontinuierliche Gruppen“. Matematika. Ann. 71: 116–144. doi:10.1007 / BF01456932.

Tento abstraktní algebra související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[FOOTNOTEDehn1911-1] Dehn 1911.

[2] Miller, Charles (1992). „Problémy s rozhodováním pro skupiny - průzkum a úvahy.“ (PDF). Algoritmy a klasifikace v kombinatorické teorii grup. Algoritmy a klasifikace v kombinatorické teorii grup (Berkeley, CA, 1989). Dodatek 3.4: Springer. s. 1–59.CS1 maint: umístění (odkaz)

[1]

[2]