Model-checking problems, machines and parameterized complexity [Elektronische Ressource] / vorgelegt von Yijia Chen

Sujets

• Informatik

Informations

• Publié par: albert-ludwigs-universitat_freiburg
• Publié le: 01 janvier 2004
• Nombre de lectures: 2
• Langue: English

Extrait

Model-Checking Problems, Machines
and Parameterized Complexity
Dissertation
zur Erlangung des Doktorgrades
der Fakult¨at fu¨r Mathematik und Physik
der Albert-Ludwigs-Universit¨at Freiburg im Breisgau
vorgelegt von
Yijia Chen
Juni 2004Dekan: Prof. Dr. Dr. h.c. Rolf Schneider
Erster Referent: Prof. Dr. Jo¨rg Flum
Zweiter Referent: Prof. Dr. Bernhard Nebel
Datum der Promotion: 20. September 2004
iiContents
1 Introduction 1
2 Preliminaries 7
2.1 First-order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Classical Complexity . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Parameterized Complexity . . . . . . . . . . . . . . . . . . 11
3 Model-Checking on Arbitrary Structures 17
3.1 Structures with Functions . . . . . . . . . . . . . . . . . . . . . . 20
3.2 A Remark on Relational Structures . . . . . . . . . . . . . . . . . 30
4 Machine Characterizations 33
4.1 The Class W[P] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.1.1 Monotone and Anti-monotone Circuits . . . . . . . . . . . 35
4.1.2 Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2 The Class W[1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 The Classes of the A-Hierarchy . . . . . . . . . . . . . . . . . . . 49
4.3.1 The Classes AWP[t] and AW[P] . . . . . . . . . . . . . . . 52
func4.4 The Classes of the W -Hierarchy . . . . . . . . . . . . . . . . . 54
4.4.1 The Class AW[*] . . . . . . . . . . . . . . . . . . . . . . . 58
4.5 The Classes of the W-Hierarchy . . . . . . . . . . . . . . . . . . . 58
5 Halting Problems 67
5.1 Short Halting Problems . . . . . . . . . . . . . . . . . . . . . . . 69
func5.1.1 Complete Halting Problems for the W -Hierarchy . . . 69
5.1.2 Complete Halting Problems for the W-Hierarchy . . . . . 74
5.1.3 Constant Space Halting Problems . . . . . . . . . . . . . 80
5.2 Compact Halting Problems . . . . . . . . . . . . . . . . . . . . . 87
A Random Access Machine 99
B Coding Issues 101
B.1 Structures and Formulas . . . . . . . . . . . . . . . . . . . . . . . 101
B.2 Turing machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
iiiiv CONTENTS
Bibliography 105
Index 109Chapter 1
Introduction
Model-checking problems, in essence, are logic problems asking if a given struc-
ture satisfies a given sentence. They are ubiquitous in computer science, al-
though appearing often in seemingly different forms. Two prominent examples
are database query and hardware verification, in which databases and hard-
ware are modelled as structures while queries and specifications as logic formu-
las. Many well-studied combinatoric problems can be reformulated as model-
checking problems as well. For example, the famous Dominating Set problem
can be translated to the model-checking problem of deciding Σ -sentences of2
first-order logic on the finite graph structures. Because of the practical im-
portance and theoretical interest, model-checking problems have been studied
intensively, particularly their associated complexity. However most results are
not so satisfying, since they show even very restricted model-checking prob-
lems already have very high complexity. Researchers have proposed different
approaches to tackle the problems and to design practically acceptable algo-
rithms. Among others Downey and Fellows introduced the parameterized com-
plexity [18], which is a refined complexity theory to deal with two-dimensional
languagesin which one part of the input instances, or parameter, is expected to
be far smaller than the other. Notice this well echoes one crucialfact about the
problems we have just mentioned: in database query, the size of most queries is
a tiny fraction of the size of any normal database; hardware, when represented
100by transitionsystems, having states ofnumber 2 , wouldhardlybe a surprise,
while real-life specifications can be written in a few lines. Based on that ob-
servation, parameterized complexity centers on a novel concept of tractability,
i.e., fixed-parameter tractability, or FPT, which, say, admits query algorithms
whoserunningtimemightbeexponential,butonlyintermsofthequeries,while
still polynomial in terms of the databases. Thereby many classical intractable
problems turn out to be fixed-parameter tractable when appropriately para-
meterized. Rich theory has been built on designing fixed-parameter tractable
algorithms [18, 42] for a great number of practical problems. But expectedly
some classical intractable problems under natural parameterization seem not
fixed-parameter tractable either. So similar to the classical NP-completeness2 Introduction
FPT→W[1]=A[1]→W[2]→W[3]→ → W[SAT] → W[P]
↓ ↓ ↓ ↓
A[2]→ A[3]→→AW[∗]→AW[SAT]→AW[P]
Figure 1.1: Parameterized complexity classes.
theory, parameterizedcomplexity has a frameworkto classify problems that are
not fixed-parameter tractable, in which a bewildering variety of parameterized
classes has been identified. Figure 1.1 give some of the most important classes.
Parameterized complexity has been developed rapidly during last ten to
fifteenyearsandmadeitswaytovariousareasofcomputerscience,forexample,
database theory [34, 44], artificial intelligence [32], and computational biology
[3, 49]. But as complexity theory is still believed to be much in its infancy, so
is the younger parameterized complexity. Many notions remain to be clarified
and consolidated. For example, there are three inequivalent definitions of the
notionoffixed-parametertractability,one ofwhichevenincludes uncomputable
problems, although sensibly. Another frequent source of confusion is the way
of defining a parameterized class, which is often given as a closure of a kernel
problem under some type of parameterized reduction which preserves fixed-
parameter tractability. Although the parameterized reduction is more refined
to preserve the structure of problems, it sometimes also seems a bit arbitraryof
choosing which type of reduction to be used to define a class. One remarkable
phenomena in classical complexity is that natural complete problems tend to
remain complete under much weaker reduction, giving a strong evidence of
the robustness of a class. However this is generally not true in parameterized
complexity. For example, the famed class W[1] has a complete problem of
checking first-order existential sentences on finite graph structures, but if we
take its closure under some kind of reduction definable by first-order logic, it
hasnochancetoinclude allfixed-parametertractableproblems,whichofcourse
include polynomial time decidable problems. In contrast, we know there are
numerousNP-complete problems under first-order reductions[39].
These problems can be mainly attributed to the lack of machine character-
izations of parameterized complexity classes. Although the kernel problems of
those classes are usually some circuit satisfiability problems and even halting
problemsofTuring machines,andone mightargue,circuits arealso“machines”
in a general sense, it is nevertheless unclear what the operational intuition is
when we combine a reduction and the kernel problem, and why the class is
intractable without assuming the intractability of the kernel problem. But tak-
ingNP as an example, it is clear that the underlying nondeterministic Turing
machines give solid evidence of its intractability, and theNP-completeness of a
problem means the hardness of the problem but notNP itself. However it is
another way around in parameterized complexity. One often encounters in the
literature of parameterized complexity an argument like3
TheproblemP isnotfixed-parametertractable,unlessW[1]=FPT,
to claim the intractability of P. This would be somehow questionable without
clear support of the naturalness of the class W[1], because it is equivalent to
that
P isnotfixed-parametertractable,unlessp-Cliqueisfixed-parameter
tractable,
where p-Clique is the parameterized version of the classical Clique problem.
Clearly the second sentence is much weaker in philosophical term.
Surely there are proven results to support W[1] = FPT. One is that the
halting problem of Turing machine, parameterized by the number of running
steps, is complete for W[1][6]. On the other hand, assuming the tractability
of W[1] there would be a subexponential time algorithm for 3Sat[18], which is
widely believed to be unlikely[40]. Nevertheless, these two results can be easily
rephrased without mentioning the class W[1] altogether.
So the main topic of our thesis is to provide clear and natural machine char-
acterizationsofdifferentparameterizedcomplexityclasses. Thestartingpointof
our work is the class W[P] which is defined to be the class of all parameterized
problems that are reducible to the weighted satisfiability problem for Boolean
circuits. This problem asks whether a given circuit has a satisfying assignment
of weight k, that is, a satisfying assignment in which precisely k inputs are set
to True. Here k is treated as the parameter of the problem. As all the other
“W-classes”in Figure 1.1 are defined similarly in terms of the weightedsatisfia-
bility problem, but for restricted classes of circuits, thus in some sense, W[P] is
one of the most natural parameterized complexity classes. Our machine char-
acterizationof