Title (eng)
Comparing the relative complexity of equivalence relations via strong reduction functions
Author
Michael Mortinger
Advisor
Sy-David Friedman
Assessor
Sy-David Friedman
Abstract (deu)
Das Ziel dieser Arbeit ist es, die relative Komplexität verschiedener Äquivalenzrelationen zu vergleichen. Dies geschieht durch so genannte starke Reduktionsfunktionen, bei denen nicht ein Tupel von einer Äquivalenzrelation auf eine andere reduziert wird, sondern die Reduktion für jedes Element einzeln angewandt wird. Diese Art von Reduktion ist besser geeignet um die Komplexität verschiedener Isomorphieprobleme zu vergleichen als die gewöhnliche Polynomzeit-Reduktion. Das erste Kapitel bietet eine kurze Einführung in einige Grundlagen der Modelltheorie und der Komplexitätstheorie. Darüber hinaus bietet es einige Beispiele für Klassen von Strukturen, die im Laufe der Arbeit zur Entwicklung unserer Theorie verwendet werden. Im zweiten Kapitel führen wir die Begriffe der starken Isomorphie-Reduzierbarkeit und der potenziellen Reduzierbarkeit ein und verwenden die Konzepte der Invariantisierung und Kanonisierung, um einen Einblick in die Struktur der starken Isomorphie-Grade zu gewinnen. Wir werden sehen, dass es eine reichhaltige Struktur gibt. Tatsächlich werden wir zeigen, dass die Struktur der starken Isomorphiegrade unterhalb der Relation LOP eine Kopie der abzählbaren atomfreien booleschen Algebra enthält. Ferner untersuchen wir, ob der Begriff der starken Isomorphie-Reduzierbarkeit <_iso und der Begriff der potentiellen Reduzierbarkeit <_pot unterschiedlich sind, und können dies nur beantworten, indem wir einige komplexitätstheoretische Annahmen tre_en. Am Ende dieses Abschnitts betrachten wir starke Reduktionsfunktionen, die es uns ermöglichen, beliebige Äquivalenzrelationen zu vergleichen. Wir verwenden dieses Konzept, um zu zeigen, dass man die Komplexitätsklassen P und #P seperieren kann, wenn man annimmt dass <_iso und <_pot verschieden sind. Kapitel 3 konzentriert sich auf vier elementare Probleme: Das Erkennungsproblem, das Invariantenproblem, das Kanonisierungsproblem und das Problem des ersten Mitglieds. Wir zeigen, dass diese Probleme von streng zunehmender Komplexität sind und dass es im Allgemeinen nicht möglich ist eines dieser Probleme auf ein früheres zu reduzieren, selbst mit Hilfe eines Orakels. Schließlich, in Kapitel 4 werden die Benchmark-Relationen id, E_lambda und E_sigma eingeführt. Wir zeigen, dass die Reduzierbarkeitshierarchie auch ohne Isomorphierelationen eine reichhaltige Struktur hat, und vergleichen sie mit der Hierarchie der starken Isomorphiegrade. Im letzten Abschnitt dieses Kapitels betrachten wir pseudo-endliche Äquivalenzrelationen, d.h. Äquivalenzrelationen mit nur endlich vielen nicht trivialen Äquivalenzklassen.
Abstract (eng)
The goal of this thesis is to compare the relative complexity of different equivalence relations. This is done by so-called strong reduction functions in which, instead of reducing a pair of elements from one equivalence relation to another, the reduction is performed on each element individually. This notion of reduction is more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphism problem for di_erent classes of structures. The first chapter provides a rough introduction to some basics of model theory and complexity theory. Furthermore it offers some examples of classes of structures which will be used to establish our framework throughout the thesis. In the second chapter we introduce the notions of strong isomorphism reducibility and potential reducibility and use the concepts of invariantization and canonization to gain some insight into the structure of strong isomorphism degrees. We will see that there is a rich structure, in fact we will show that the structure of strong isomorphism degrees below the relation LOP contains a copy of the countable atomless boolean algebra. Further, we investigate whether the notion of strong isomorphism redction <_iso and the notion of potential reducibility <_pot are distinct and can only answer this by making some complexity theoretical assumption. At the end of this section we look at strong reduction functions that allows us to compare arbitrary equivalence relations. We use this concept to show that one can separate the complexity classes P and #P assuming that <_iso and <_pot are distinct. Chapter 3 focuses on four elementary problems: The recognition problem, the invariant problem, the canonization problem and the first member problem. We show that those problems are of strictly increasing complexity and that it is not possible in general to reduce one of these problems to an earlier one even with the help of an oracle. Finally, in chapter 4 the benchmark relations id ,E_lambda and E_sigma are introduced. We show that the reducibility hierarchy, even when considering only equivalence relations apart from isomorphism relations, has a rich structure and compare it to our established hierarchy of strong isomorphism degrees. In the last section of this chapter we look at finitary equivalence relations, which are equivalence relations with only _nitely many non trivial equivalence classes, i.e. only finitely many equivalence classes consist of more than one element.
Keywords (deu)
KomplexitätstheorieEquivalenzrelationen
Keywords (eng)
Complexity TheoryEquivalence Relations
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1604290
rdau:P60550 (deu)
v, 53 Seiten : Diagramme
Number of pages
61
Association (deu)
Title (eng)
Comparing the relative complexity of equivalence relations via strong reduction functions
Author
Michael Mortinger
Abstract (deu)
Das Ziel dieser Arbeit ist es, die relative Komplexität verschiedener Äquivalenzrelationen zu vergleichen. Dies geschieht durch so genannte starke Reduktionsfunktionen, bei denen nicht ein Tupel von einer Äquivalenzrelation auf eine andere reduziert wird, sondern die Reduktion für jedes Element einzeln angewandt wird. Diese Art von Reduktion ist besser geeignet um die Komplexität verschiedener Isomorphieprobleme zu vergleichen als die gewöhnliche Polynomzeit-Reduktion. Das erste Kapitel bietet eine kurze Einführung in einige Grundlagen der Modelltheorie und der Komplexitätstheorie. Darüber hinaus bietet es einige Beispiele für Klassen von Strukturen, die im Laufe der Arbeit zur Entwicklung unserer Theorie verwendet werden. Im zweiten Kapitel führen wir die Begriffe der starken Isomorphie-Reduzierbarkeit und der potenziellen Reduzierbarkeit ein und verwenden die Konzepte der Invariantisierung und Kanonisierung, um einen Einblick in die Struktur der starken Isomorphie-Grade zu gewinnen. Wir werden sehen, dass es eine reichhaltige Struktur gibt. Tatsächlich werden wir zeigen, dass die Struktur der starken Isomorphiegrade unterhalb der Relation LOP eine Kopie der abzählbaren atomfreien booleschen Algebra enthält. Ferner untersuchen wir, ob der Begriff der starken Isomorphie-Reduzierbarkeit <_iso und der Begriff der potentiellen Reduzierbarkeit <_pot unterschiedlich sind, und können dies nur beantworten, indem wir einige komplexitätstheoretische Annahmen tre_en. Am Ende dieses Abschnitts betrachten wir starke Reduktionsfunktionen, die es uns ermöglichen, beliebige Äquivalenzrelationen zu vergleichen. Wir verwenden dieses Konzept, um zu zeigen, dass man die Komplexitätsklassen P und #P seperieren kann, wenn man annimmt dass <_iso und <_pot verschieden sind. Kapitel 3 konzentriert sich auf vier elementare Probleme: Das Erkennungsproblem, das Invariantenproblem, das Kanonisierungsproblem und das Problem des ersten Mitglieds. Wir zeigen, dass diese Probleme von streng zunehmender Komplexität sind und dass es im Allgemeinen nicht möglich ist eines dieser Probleme auf ein früheres zu reduzieren, selbst mit Hilfe eines Orakels. Schließlich, in Kapitel 4 werden die Benchmark-Relationen id, E_lambda und E_sigma eingeführt. Wir zeigen, dass die Reduzierbarkeitshierarchie auch ohne Isomorphierelationen eine reichhaltige Struktur hat, und vergleichen sie mit der Hierarchie der starken Isomorphiegrade. Im letzten Abschnitt dieses Kapitels betrachten wir pseudo-endliche Äquivalenzrelationen, d.h. Äquivalenzrelationen mit nur endlich vielen nicht trivialen Äquivalenzklassen.
Abstract (eng)
The goal of this thesis is to compare the relative complexity of different equivalence relations. This is done by so-called strong reduction functions in which, instead of reducing a pair of elements from one equivalence relation to another, the reduction is performed on each element individually. This notion of reduction is more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphism problem for di_erent classes of structures. The first chapter provides a rough introduction to some basics of model theory and complexity theory. Furthermore it offers some examples of classes of structures which will be used to establish our framework throughout the thesis. In the second chapter we introduce the notions of strong isomorphism reducibility and potential reducibility and use the concepts of invariantization and canonization to gain some insight into the structure of strong isomorphism degrees. We will see that there is a rich structure, in fact we will show that the structure of strong isomorphism degrees below the relation LOP contains a copy of the countable atomless boolean algebra. Further, we investigate whether the notion of strong isomorphism redction <_iso and the notion of potential reducibility <_pot are distinct and can only answer this by making some complexity theoretical assumption. At the end of this section we look at strong reduction functions that allows us to compare arbitrary equivalence relations. We use this concept to show that one can separate the complexity classes P and #P assuming that <_iso and <_pot are distinct. Chapter 3 focuses on four elementary problems: The recognition problem, the invariant problem, the canonization problem and the first member problem. We show that those problems are of strictly increasing complexity and that it is not possible in general to reduce one of these problems to an earlier one even with the help of an oracle. Finally, in chapter 4 the benchmark relations id ,E_lambda and E_sigma are introduced. We show that the reducibility hierarchy, even when considering only equivalence relations apart from isomorphism relations, has a rich structure and compare it to our established hierarchy of strong isomorphism degrees. In the last section of this chapter we look at finitary equivalence relations, which are equivalence relations with only _nitely many non trivial equivalence classes, i.e. only finitely many equivalence classes consist of more than one element.
Keywords (deu)
KomplexitätstheorieEquivalenzrelationen
Keywords (eng)
Complexity TheoryEquivalence Relations
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1611456
Number of pages
61
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0