Testování identit

• Název práce v češtině: Testování identit
• Název v anglickém jazyce: Identity checking
• Akademický rok vypsání: 2005/2006
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. RNDr. David Stanovský, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 14.11.2005
• Datum zadání: 14.11.2005
• Datum a čas obhajoby: 28.06.2006 00:00
• Datum odevzdání elektronické podoby: 28.06.2006
• Datum odevzdání tištěné podoby: 28.06.2006
• Datum proběhlé obhajoby: 28.06.2006
• Oponenti: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.

Zásady pro vypracování

Na ověření, zda daná identita (např. komutativita, asociativita, apod.) platí v dané algebře (grupě, pologrupě, okruhu,...), existuje očividný algoritmus, který má exponenciální složitost vzhledem k délce zadané identity (pro fixní algebru). Není těžké nahlédnout, že tento problém je pro libovolnou algebru v třídě coNP a že existují algebry, pro které je coNP-úplný. Na druhou stranu, pro mnoho algeber (např. pro abelovské grupy) existuje algoritmus polynomiální. Existuje mezinárodní projekt, jehož cílem je charakterizovat ty algebry, pro které je tento problém polynomiální, resp. coNP-úplný. Cílem práce je sumarizovat některé známé výsledky o grupách a/nebo pologrupách a/nebo okruzích.

Seznam odborné literatury

Burris, Stanley; Lawrence, John. The equivalence problem for finite rings. J. Symbolic Comput. 15 (1993), no. 1, 67--71.
Burris, Stanley; Lawrence, John. Results on the equivalence problem for finite groups. Algebra Universalis 52 (2004), no. 4, 495--500 (2005).
Horváth G., Szabó Cs. The complexity of checking identities over finite groups. Preprint 2005.
a další literatura dle pokynů vedoucího