Model-checking problems, machines and parameterized complexity

Parameterized complexity is a new approach to deal with classical <br>intractable problem. It is built on a novel notion of <br>tractability, i.e., fixed-parameter tractability, which <br>admits algorithms that have exponential running time, but <br>just in terms of parameter of the problem instance that <br>is expected to be small in the typical applications. <br>Significant progress has been made to identify those <br>classical intractable problems that have fixed-parameter <br>tractable algorithms. Meanwhile a great number of parameterized <br>intractable classes has been identified to classify problems that <br>seem fixed-parameter intractable, <br>which resembles the classical NP-completeness theory. <br>However almost all <br>those classes are defined as closures of kernel problems <br>under some type of reductions. <br> <br>The main topic of our thesis is to provide natural machine <br>characterizations of all major parameterized classes. The starting <br>point is the class W[P], which we characterize as the languages <br>that are decidable by nondeterministic fixed-parameter <br>tractable algorithms of random access machines whose use of <br>nondeterminism is bounded in terms of the parameters. By <br>further tuning the nondeterminism that the random access machines can use, <br>say, allowing alternating, or restricting the access to <br>the guessed numbers, we obtain machine characterizations of <br>almost all important parameterized complexity classes. <br>We also investigate some structural issues <br>of parameterized complexity in the light of these <br>machine characterizations. <br> <br>Our main technical tools are model-checking problems. <br>The parameterized classes we deal with are originally defined <br>via various satisfiability problems or halting problems <br>of Turing machines. However there are model-checking problems of <br>natural fragments of first-order logic complete for some <br>of the most important classes. And model-checking problems <br>are much more manageable than those hard combinatorics <br>required to deal with those classes when using the original <br>definitions. On the other hand parameterized complexity <br>has proved to be a more appropriate framework of analysing <br>the complexity of model-checking problems. We investigate model-checking <br>problems on structures with functions, while most previous <br>works study relational structures. Based on that we introduce <br>a new hierarchy of classes and prove some basic complete results <br>and give their machine characterizations. <br> <br>Finally we also study the halting problems of Turing machines <br>in the context of parameterized complexity. It is previous known <br>that some natural halting problems are complete for some <br>parameterized classes. We give halting problems of other important <br>classes.

Author dc:creator

• Chen, Yijia

Contributors dc:contributor

• Flum, Jörg

• Model-Checking
• Machine
• Parameterized Complexity

Repository record source_url

https://freidok.uni-freiburg.de/data/1457

OAI identifier oai:identifier

oai:freidok.uni-freiburg.de:1457