Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-143 | 3rd November 2014 14:50

Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

RSS-Feed




TR14-143
Authors: Ronald de Haan, Stefan Szeider
Publication: 3rd November 2014 15:55
Downloads: 2356
Keywords: 


Abstract:

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These parameterized problems are based on problems whose complexity lies at the second level of the Polynomial Hierarchy or higher. The list will be updated as necessary.



ISSN 1433-8092 | Imprint