M. B.:
On the Space and Circuit Complexity of Certain Parameterized Problems.
Universität zu Lübeck, Institut für Theoretische Informatik,
2014.
Supervised by: Till Tantau, Maciej Liskiewicz.
Show PDF | Show abstract
Parameterized complexity theory provides important tools to generate and an- alyze reasonable fast algorithms for hard problems. Current research mainly focuses on the question whether parameterized problems are fixed-parameter tractable or not, i. e., if there is a fast algorithm solving them. Thus, the only considered resource is time, while parameterized space and circuit complexity is often omitted, although these resources are useful in classical complexity the- ory as well. A recent work from Elberfeld, Stockhusen, and Tantau provides a framework of parameterized space and circuit classes to cover this area [26]. Al- though the framework provides parameterized space and circuit classes, as well as tools to analyze them, there is still a lack of complete problems for most of these classes. The objective of this thesis is to resolve this issue by analyzing widely known problems with respect to the framework and, thus, populate the different classes. This will lead to new upper bounds for many natural prob- lems, together with a couple of new lower bounds for some of them. Moreover, we will also be able to collide the upper and lower bounds of some of these problems and, hence, finally resolve the complexity of them.
