The structure of graphs and new logics for the characterization of Polynomial Time [Elektronische Ressource] / Bastian Laubner. Gutachter: Martin Grohe ; Erich Grädel ; Anuj Dawar

M.Sc. Bastian Laubner

Sujets

• Informatik
• Mathematics

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2011
• Nombre de lectures: 30
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

The Structure of Graphs and New Logics for the
Characterization of Polynomial Time
DISSERTATION
zur Erlangung des akademischen Grades
Doctor Rerum Naturalium
im Fach Informatik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultät II
Humboldt-Universität zu Berlin
von
M.Sc. Bastian Laubner
geboren am 2. März 1982 in Berlin
Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs
‘Methods for Discrete Structures’ (GRK 1408)
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Jan-Hendrik Olbertz
Dekan der Mathematisch-Naturwissenschaftlichen Fakultät II:
Prof. Dr. Peter Frensch
Gutachter:
1. Prof. Dr. Martin Grohe
2. Prof. Dr. Erich Grädel
3. Prof. Dr. Anuj Dawar
eingereicht am: 22. November 2010
Tag der mündlichen Prüfung: 23. Februar 2011Zusammenfassung
Die deskriptive Komplexitätstheorie ist der Bereich der theoretischen Informatik, der sich mit
abstrakten Charakterisierungen von maschinellen Berechnungen durch mathematische Logiken
beschäftigt. Ähnlich der gewöhnlichen Komplexitätstheorie ist das Ziel, Berechnungsprobleme
anhand der Ressourcen zu klassifizieren, die für ihre Lösung benötigt werden. Anstelle von ma-
schinellen betrachtet die deskriptive Komplexitätstheorie jedoch die logische Aus-
drucksstärke, die benötigt wird, um eine Klasse von Problemen zu definieren. Der Zweck be-
steht darin, alternative Charakterisierungen von Komplexitätsklassen zu finden, mit denen sich
die Stärken und Schwächen von maschinellen Berechnungen ohne Bezugnahme auf das konkrete
Berechnungsmodell untersuchen lassen.
Diese Arbeit leistet einen Beitrag zu drei Teilgebieten der deskriptiven Komplexitätstheorie.
Zunächst betrachten wir ein Missverhältnis zwischen maschinellen Berechnungen, deren Einga-
be stets aus geordneten Wörtern besteht, und logischen Definitionen, deren abstrakte Betrachtung
von Eingabestrukturen ohne Ordnung auskommt. Wir zeigen, dass ein kombinatorischer Graph-
kanonisierungsalgorithmus mit einfach exponentieller Laufzeit von Corneil und Goldberg (1984)
auf kantengefärbte Graphen ausgeweitet werden kann. Die Repräsentationsinvarianz dieses Al-
gorithmus gestattet uns die Implementierung in der Logik „Choiceless Polynomial Time with
˜Counting“ (CPT+C) bei Beschränkung auf logarithmisch große Fragmente solcher Graphen. Auf
˜Strukturen, deren Relationen höchstens Stelligkeit 2 haben, charakterisiert CPT+C damit gerade
die Polynomialzeit-Eigenschaften (PTIME) von Fragmenten logarithmischer Größe.
Der zweite Beitrag untersucht die deskriptive Komplexität von PTIME-Berechnungen auf ein-
geschränkten Graphklassen. Wir stellen eine neuartige Normalform von Intervallgraphen vor, die
sich in Fixpunktlogik mit Zählen (FP+C) definieren lässt, was bedeutet, dass FP+C auf dieser
Graphklasse PTIME charakterisiert. Die Methoden, die wir dafür entwickeln, machen erstmals
die modulare Zerlegung von Graphen nutzbar für eine systematische Ergründung des Verhält-
nisses zwischen Logiken und Komplexitätsklassen. Wir führen anschließend das Konzept von
„Non-Capturing“-Reduktionen ein, das uns zu einer Reihe von Graphklassen führt, auf denen
das Einfangen von Komplexitätsklassen genau so schwer ist wie auf der Klasse aller Graphen.
Schließlich adaptieren wir unsere Methoden, um einen kanonischen Beschriftungsalgorithmus
für Intervallgraphen zu erhalten, der sich mit logarithmischer Platzbeschränkung (LOGSPACE)
berechnen lässt. Wir ziehen den Schluss, dass das Intervallgraphen-Isomorphieproblem vollstän-
dig ist für die Klasse LOGSPACE. Auf diese Art leisten unsere logischen Methoden einen Beitrag
zur klassischen Komplexitätstheorie.
Im dritten Teil dieser Arbeit beschäftigt uns die ungelöste Frage, ob es eine Logik gibt, die
alle Polynomialzeit-Berechnungen charakterisiert. Wir führen eine Reihe von Ranglogiken ein,
die die Fähigkeit besitzen, den Rang von Matrizen über Primkörpern zu berechnen. Wir zeigen,
dass diese Ergänzung um lineare Algebra robuste Logiken hervor bringt, und dass diese die Aus-
drucksstärke vonFP+C und vielen anderen Logiken übertreffen, die im Zusammenhang mit dieser
Frage betrachtet werden. Durch Anpassung einer Konstruktion von Hella (1996) gelingt es uns
außerdem zu beweisen, dass Ranglogiken strikt an Ausdrucksstärke gewinnen, wenn wir die Zahl
an Variablen erhöhen, die die betrachteten Matrizen indizieren. Wir rechtfertigen unsere spezi-
elle Wahl von Rangberechnungen dadurch, dass die meisten klassischen Probleme der linearen
Algebra entweder in Ranglogiken oder bereits in FP+C definierbar sind. Dann bauen wir eine
Brücke zur klassischen Komplexitätstheorie, indem wir über geordneten Strukturen eine Reihe
von Komplexitätsklassen zwischen LOGSPACE und PTIME durch Ranglogiken charakterisie-
ren. Unsere Arbeit etabliert die stärkste unserer Ranglogiken als Kandidat für die Charakterisie-
rung von PTIME und legt nahe, dass Ranglogiken genauer erforscht werden müssen, um weitere
Fortschritte zu erzielen im Hinblick auf eine Logik für Polynomialzeit.
iiiAbstract
Descriptive complexity theory is the area of theoretical computer science that is concerned with
the abstract characterization of computations by means of mathematical logics. It shares the ap-
proach of complexity theory to classify problems on the basis of the resources that are needed to
solve them. Instead of computational resources, however, descriptive complexity theory considers
the expressiveness necessary for a logic to define classes of problems. Its primary goal is to pro-
vide alternative characterizations of computational complexity that give us a way to reason about
the strengths and limitations of procedures without reference to the underlying
machine model.
This thesis is making contributions to three strands of descriptive complexity theory. First,
we consider an incongruence between machine computations, which receive ordered strings as
their input, and logics, whose abstract view on input structures omits the ordering. We show that
a combinatorial, singly exponential-time graph canonization algorithm of Corneil and Goldberg
(1984) can be extended to edge-colored directed graphs. The algorithm’s input invariance allows
˜us to implement it in the logic Choiceless Polynomial Time with Counting (CPT+C) if we restrict
our attention to logarithmic-sized fragments of such graphs. This means that on structures whose
relations are of arity at most 2, the polynomial-time (PTIME) properties of logarithmic-sized
˜fragments are precisely characterized by CPT+C.
The second contribution investigates the descriptive complexity of PTIME computations on re-
stricted classes of graphs. We present a novel canonical form for the class of interval graphs which
is definable in fixed-point logic with counting (FP+C), resulting inFP+C capturing PTIME on this
graph class. The methods developed for this result may serve as the foundation for a systematic
study of the interrelation of logics and complexity classes on the basis of modular decompositions
of graphs. Then we introduce the notion of non-capturing reductions that lead us to a wide vari-
ety of graph classes on which computational problems are equally hard to characterize as on the
class of all graphs. We finally mold our methods into a canonical labeling algorithm for interval
graphs which is computable in logarithmic space (LOGSPACE) and we draw the conclusion that
interval graph isomorphism is complete for LOGSPACE. In this way, our methods developed for
the logical domain make a contribution to classical complexity theory.
In the final part of this thesis, we take aim at the open question whether there exists a logic
which generally captures polynomial-time computations. We introduce a variety of rank logics
with the ability to compute the ranks of matrices over (finite) prime fields. We argue that this
introduction of linear algebra makes for a robust notion of a logic and that it increases the expres-
siveness ofFP+C and many other logics considered in the context of capturing PTIME. By adapt-
ing a construction of Hella (1996), we establish that rank logics strictly gain in expressiveness
when we increase the number of variables that index the matrices we consider. Rank computa-
tions are the first natural operation for which this property is shown in the presence of recursion.
Our particular choice of rank computations is justified by showing that most classic problems in
linear algebra can either be defined by rank logics or are already definable in FP+C. Then we
establish a direct connection to standard complexity theory by showing that in the presence of
orders, a variety of complexity classes between LOGSPACE and PTIME can be characterized by
suitably defined rank logics. Our exposition provides evidence that rank logics are a natural object
to study and establishes the most expressive of our rank logics as a viable candidate for capturing
PTIME, suggesting that rank logics need to be better understood if progress is to be made towards
a logic for polynomial time.
ivAcknowledgements
I am indebted to my supervi