| Autor(en): |
Kord Eickmeyer |
Titel: |
Randomness in complexity theory and logics |
| Gutachter: |
Martin Grohe; Nicole Schweikardt; Peter Bro Miltersen |
| Erscheinungsdatum: |
01.09.2011 |
| Volltext: |
pdf
(urn:nbn:de:kobv:11-100192373)
|
| Fachgebiet(e): |
Informatik |
| Schlagwörter (ger): |
Randomisierung, deskriptive Komplexitätstheorie, Derandomisierung, Logik, endliche Modelltheorie |
| Schlagwörter (eng): |
descriptive complexity theory, randomisation, derandmisation, logics, finite model theory |
| Einrichtung: |
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II |
| Lizenz: |
|
| Zitationshinweis: |
Eickmeyer, Kord:
Randomness in complexity theory and logics;
Dissertation,
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 01.09.2011, urn:nbn:de:kobv:11-100192373
|
Metadatenexport:
 Um
den gesamten Metadatensatz im Endnote- oder
Bibtex-Format zu speichern,
klicken Sie bitte auf den entsprechenden Link.
|
Endnote
Bibtex
|
| print on demand:
Wenn
Sie auf dieses Icon klicken, können Sie
ein Druckexemplar dieser Publikation bestellen.
|
|
| Diese Seite taggen:
Diese
Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie
Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer
ansehen können.
|
|
| Abstract (ger): |
| Die vorliegende Dissertation besteht aus zwei Teilen, deren
gemeinsames Thema in der Frage besteht, wie mächtig Zufall als
Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit
zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit --
Eigenschaften haben können, die von Computeralgorithmen genutzt werden
können. In zwei konkreten Fällen geben wir bis dahin unbekannte
deterministische Konstruktionen solcher Strukturen: Wir
derandomisieren eine randomisierte Reduktion von Alekhnovich und
Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen
konstruieren, und wir geben eine Reduktion von einem Problem über
bipartite Graphen auf das Problem, den minmax-Wert in
Dreipersonenspielen zu berechnen.
Im zweiten Teil
untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie
durch zufällige Relationssymbole angereichert werden. Unser Ziel ist
es, Techniken aus der deskriptiven Komplexitätstheorie für die
Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und
tatsächlich können wir zeigen, dass unsere randomisierten Logiken
randomisierte Komlexitätsklassen einfangen, die in der
Komplexitätstheorie untersucht werden. Unter Benutzung starker
Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von
Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch
negative Derandomisierungsergebnisse für unsere Logiken. Auf der
negativen Seite zeigen wir, dass randomisierte erststufige Logik
gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt,
sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem
ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger
Logik enthalten, und auch nicht in infinitärer Zähllogik auf
beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass
randomisierte erststufige Logik auf Strukturen mit einem unären
Vokabular derandomisiert werden kann und auf additiven Strukturen in
monadischer Logik zweiter Stufe enthalten ist.
|
| Abstract (eng): |
| This thesis is comprised of two main parts whose common theme is the
question of how powerful randomness as a computational resource is. In
the first part we deal with random structures which possess -- with high
probability -- properties than can be exploited by computer
algorithms. We then give two new deterministic constructions for such
structures: We derandomise a randomised reduction due to Alekhnovich
and Razborov by constructing certain unbalanced bipartite expander
graphs, and we give a reduction from a problem concerning bipartite
graphs to the problem of computing the minmax-value in three-player
games.
In the second part we study the expressive power of various
logics when they are enriched by random relation symbols. Our goal is
to bridge techniques from descriptive complexity with the study of
randomised complexity classes, and indeed we show that our randomised
logics do capture complexity classes under study in complexity
theory. Using strong results on the expressive power of first-order
logic and the computational power of bounded-depth circuits, we give
both positive and negative derandomisation results for our logics. On
the negative side, we show that randomised first-order logic gains
expressive power over standard first-order logic even on structures
with a built-in addition relation. Furthermore, it is not contained in
monadic second-order logic on ordered structures, nor in infinitary
counting logic on arbitrary structures. On the positive side, we show
that randomised first-order logic can be derandomised on structures
with a unary vocabulary and is contained in monadic second-order logic
on additive structures.
|
Zugriffsstatistik:
Die Daten für die Zugriffsstatistik der einzelnen Dokumente
wurden aus den durch AWStats aggregierten Webserver-Logs erstellt.
Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie
auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen
(insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert
auf eine der Dateien (Kapitel) des Dokuments angezeigt.
Um die detaillierten Zugriffszahlen zu sehen,
fahren Sie bitte mit dem Mauszeiger
über die einzelnen Balken des Diagramms.
|
  | | | | | | | | | | | | | | | | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 |
| Monat | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 | | Startseite | 10 | 1 | 3 | | | | | | 3 | | | | | | | 3 | | PDF | 23 | 4 | 4 | 9 | 14 | 13 | 13 | 16 | 14 | 8 | 7 | 8 | 10 | 9 | 24 | 31 |
Gesamtzahl der Zugriffe seit Sep 2011: - Startseite – 20 (1.25 pro Monat)
- PDF – 207 (12.94 pro Monat)
|
