• Startseite
• Recherche
• Veröffentlichen
• Hilfe

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-14576
URL: http://www.freidok.uni-freiburg.de/volltexte/1457/

Chen, Yijia

Model-checking problems, machines and parameterized complexity

Model-Checking-Probleme, Maschinen und Parametrische Komplexitätstheorie

Kurzfassung in Englisch

Parameterized complexity is a new approach to deal with classical
intractable problem. It is built on a novel notion of
tractability, i.e., fixed-parameter tractability, which
admits algorithms that have exponential running time, but
just in terms of parameter of the problem instance that
is expected to be small in the typical applications.
Significant progress has been made to identify those
classical intractable problems that have fixed-parameter
tractable algorithms. Meanwhile a great number of parameterized
intractable classes has been identified to classify problems that
seem fixed-parameter intractable,
which resembles the classical NP-completeness theory.
However almost all
those classes are defined as closures of kernel problems
under some type of reductions.

The main topic of our thesis is to provide natural machine
characterizations of all major parameterized classes. The starting
point is the class W[P], which we characterize as the languages
that are decidable by nondeterministic fixed-parameter
tractable algorithms of random access machines whose use of
nondeterminism is bounded in terms of the parameters. By
further tuning the nondeterminism that the random access machines can use,
say, allowing alternating, or restricting the access to
the guessed numbers, we obtain machine characterizations of
almost all important parameterized complexity classes.
We also investigate some structural issues
of parameterized complexity in the light of these
machine characterizations.

Our main technical tools are model-checking problems.
The parameterized classes we deal with are originally defined
via various satisfiability problems or halting problems
of Turing machines. However there are model-checking problems of
natural fragments of first-order logic complete for some
of the most important classes. And model-checking problems
are much more manageable than those hard combinatorics
required to deal with those classes when using the original
definitions. On the other hand parameterized complexity
has proved to be a more appropriate framework of analysing
the complexity of model-checking problems. We investigate model-checking
problems on structures with functions, while most previous
works study relational structures. Based on that we introduce
a new hierarchy of classes and prove some basic complete results
and give their machine characterizations.

Finally we also study the halting problems of Turing machines
in the context of parameterized complexity. It is previous known
that some natural halting problems are complete for some
parameterized classes. We give halting problems of other important
classes.

Kurzfassung in Deutsch

Wir geben Maschinencharakterisierung von die parametrischer Komplexitätsklassen. Wir studieren auch die Halting-Probleme
im Kontext der parametrische Komplexitätstheorie.