Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-12033
Autor(en): | Weiß, Armin |
Titel: | Circuit complexity of group theoretic problems |
Sonstige Titel: | Schaltkreiskomplexität gruppentheoretischer Probleme |
Erscheinungsdatum: | 2021 |
Dokumentart: | Habilitation |
Seiten: | XVI, 49 |
URI: | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-120506 http://elib.uni-stuttgart.de/handle/11682/12050 http://dx.doi.org/10.18419/opus-12033 |
Zusammenfassung: | In dieser kumulativen Habilitationsschrift werden sechs Arbeiten zum Thema "Schaltkreiskomplexität von Gruppentheoretischen Problemen" zusammengefasst. An vorderster Stelle steht hierbei das Wortproblem: Gegeben ein Wort über den Erzeugern einer Gruppe, ist die Frage, ob das Wort das Einselement der Gruppe darstellt. Daneben werden noch weitere Probleme, wie das Konjugationsproblem, das Power-Wortproblem (wie das Wortproblem, aber die Eingabe wird in komprimierter Form gegeben) und das Lösen von Gleichungen betrachtet. Die meisten der hier zusammengefassten Arbeiten betrachten die genannten Probleme für spezielle Klassen von Gruppen und klassifizieren deren Komplexität mit Methoden der Schaltkreiskomplexität. Eine Ausnahme bildet die letzte Arbeit zum Thema Gleichungen: hier liegt der Zusammenhang zur Schaltkreiskomplexität darin, dass sich das Erfüllbarkeitsproblem für Gleichungen in endlichen auslösbaren Gruppen ähnlich verhält wie das Erfüllbarkeitsproblem für CC^0 Schaltkreise. |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
entwurf_FINAL.pdf | 832,55 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.