Bachelorarbeit BCLR-2023-82

Bibliograph.
Daten
Kurz, Maximilian: Kranzprodukte und MOD-Klassen.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 82 (2023).
41 Seiten, deutsch.
Kurzfassung

Definiert man formale Sprachen im Bezug auf die Akzeptanzbedingungen oder Blattsprachen der nicht-deterministischen Turingmaschinen, von denen diese erkannt werden, so erhält man sogenannte Countingclasses [Ric92]. Bekannte Vertreter dieser Klassen sind NP, coNP, oder !P. Dabei sind sämtliche Countingclasses Unterklassen von P#V[1], also der Klasse von Sprachen, welche durch eine nicht-deterministische Turingmaschine mit polynomieller Laufzeit und genau einem Zugriff auf ein #P-Orakel erkannt werden können. Wählt man als Akzeptanzbedingung beispielsweise die Teilbarkeit der Anzahl von akzeptierenden Pfaden einer nicht-deterministischen Turingmaschine mit polynomiell beschränkter Laufzeit durch eine ganze Zahl :, so erhält man die Klasse coMod:P. Die Elemente der Blätter des Berechnungsbaumes einer nicht-deterministischen Turingmaschine können aber auch genauer spezifiziert werden. Interpretiert man die Blattinhalte als Elemente einer Gruppe ⌧, und definiert als Akzeptanzbedingung der Maschine, dass sich das Blattwort in ⌧ zu 1⌧ auswertet, so erhält man die Klasse (⌧)P. Zur Einführung zeigen wir einige bereits bekannte und nützliche Abschlusseigenschaften von Mod:P und ähnlichen Klassen, und gehen dann im folgenden Kapitel auf Zusammenhänge zwischen coMod:P und (Z/:Z)P sowie (⌧)P ein. In Kapitel 4 beschäftigen wir uns mit der Klasse (⌧)P, zuerst für zyklische Gruppen, und später für beliebige endliche abelsche Gruppen. Gegen Ende dieses Kapitels untersuchen wir die Wirkung semidirekter Produkte von Gruppen auf unserer Resultate, und erweitern schließlich unsere Konstruktion auf Kranzprodukte.

Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
BetreuerWeiß, Dr. Armin
Eingabedatum4. April 2024
   Publ. Abteilung   Publ. Institut   Publ. Informatik