Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FIRST-ORDER SENTENCE:
Reports tagged with first-order sentence:
TR07-001 | 19th November 2006
Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

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

Revisions: 1

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




ISSN 1433-8092 | Imprint