• Media type: E-Book; Electronic Thesis; Doctoral Thesis
  • Title: Randomness in complexity theory and logics
  • Contributor: Eickmeyer, Kord [Author]
  • imprint: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2011-09-01
  • Language: English
  • DOI: https://doi.org/10.18452/16364
  • Keywords: randomisation ; finite model theory ; deskriptive Komplexitätstheorie ; Randomisierung ; 28 Informatik ; endliche Modelltheorie ; SK 890 ; Derandomisierung ; logics ; Logik ; derandmisation ; ST 134 ; Datenverarbeitung ; descriptive complexity theory
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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. ; This thesis is comprised of two main parts whose common theme is ...
  • Access State: Open Access
  • Rights information: Attribution - Non Commercial - No Derivs (CC BY-NC-ND)