Testování identit

• Thesis title in Czech: Testování identit
• Thesis title in English: Identity checking
• Academic year of topic announcement: 2005/2006
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Algebra (32-KA)
• Supervisor: doc. RNDr. David Stanovský, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 14.11.2005
• Date of assignment: 14.11.2005
• Date and time of defence: 28.06.2006 00:00
• Date of electronic submission: 28.06.2006
• Date of submission of printed version: 28.06.2006
• Date of proceeded defence: 28.06.2006
• Opponents: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.

Guidelines

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.

References

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