Abstract
Parameterized complexity theory studies the computational complexity of computational problems from a multivariate 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 NPcomplete 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 timespace bounds, something that is not possible in classical computational complexity if we focus on wellestablished 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 longstanding open problem of parameterized complexity.
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 timespace bounds, something that is not possible in classical computational complexity if we focus on wellestablished 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 longstanding open problem of parameterized complexity.
Originalsprache  Englisch 

Qualifikation  Doctorate 
Gradverleihende Hochschule  
Betreuer/in / Berater/in 

Publikationsstatus  Veröffentlicht  24.01.2017 