Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-130 | 11th August 2015 15:08

An Overview of Non-Uniform Parameterized Complexity

RSS-Feed




TR15-130
Authors: Ronald de Haan
Publication: 12th August 2015 04:36
Downloads: 387
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint