Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with weft hierarchy:
TR07-001 | 19th November 2006
Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution

Revisions: 2

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>>

TR14-143 | 3rd November 2014
Ronald de Haan, Stefan Szeider

Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

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 ... more >>>

ISSN 1433-8092 | Imprint