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