Parameterized Parallel Complexity
Master's defense by Noy Rotbart
We investigate whether parameterized complexity theory can shed light on the hardness of inherently sequential problems. In particular, we present an overview of both parallel and parameterized complexity, and survey known connections between the two. We then attempt to define new parameterized parallel complexity classes to improve these connections.
Finally, we introduce a new parameterized parallel complexity class, FPNC0, which is proven useful for parameterizing P-complete problems.
Supervisor: Jakob Grue Simonsen, DIKU
Censor: Lars Kristiansen, University of Oslo