Model-checking problems, machines and parameterized complexity.
Yijia Chen · FreiDok plus (Universitätsbibliothek Freiburg) · 2004
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.