Bachelor Thesis BCLR-2023-82

BibliographyKurz, Maximilian: Kranzprodukte und MOD-Klassen.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 82 (2023).
41 pages, german.
Abstract

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.

Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Weiß, Dr. Armin
Entry dateApril 4, 2024
New Report   New Article   New Monograph   Computer Science