On the Space and Circuit Complexity of Parameterized Problems

Parameterized complexity theory studies the computational complexity of computational problems from a multi-variate point of view: Instead of only measuring the amount of resources required to solve a problem relative to the size of the input, parameterized complexity also measures them relative to many other parameters of the input. Since its introduction, parameterized complexity theory has been a fruitful field, giving many important insights into the complexity of computational problems, especially by refining our knowledge about NP-complete problems. Being a relatively young field, however, parameterized complexity theory has not yet properly investigated two important aspects of complexity: space complexity and circuit complexity. While parameterized complexity theory mainly builds on time as the central resource, this thesis discusses the importance of space and circuit complexity in a parameterized setting.
After an introduction of natural parameterized space and circuit classes, we study their relation to parameterized time classes, and we will see that many parameterized problems can be better classified using parameterized space and circuit classes instead of parameterized time classes. Inspired by the Weft- Hierarchy, we study the concept of bounded nondeterminism with respect to space and circuits from a parameterized point of view, and we show that the resulting classes capture the complexity of natural problems like the associative generability problem exactly. Finally, we study classes of simultaneous time-space bounds, something that is not possible in classical computational complexity if we focus on well-established classes like polynomial time and logarithmic space, and we show that these classes capture exactly the complexity of natural problems like the longest common subsequence problem, answering a long-standing open problem of parameterized complexity.