An Overview of Non-Uniform Parameterized Complexity.
Ronald de Haan · Electronic colloquium on computational complexity · 2015
We consider several non-uniform variants of parameterized complexity classes that have been considered in the literature. We do so in a homogenous notation, allowing a clear comparison of the various variants. Additionally, we consider some novel (non-uniform) parameterized complexity classes that come up in the framework of parameterized knowledge compilation. We provide some (inclusion and separation) results relating the different non-uniform classes to each other. Moreover, we illustrate how these non-uniform parameterized complexity classes are useful in the setting of parameterized knowledge compilation.