Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with complexity gap:
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 >>>

TR09-014 | 7th February 2009
Soren Riis

On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity

We show that the asymptotic complexity of uniformly generated (expressible in First-Order (FO) logic) propositional tautologies for the Nullstellensatz proof system (NS) as well as for Polynomial Calculus, (PC) has four distinct types of asymptotic behavior over fields of finite characteristic. More precisely, based on some highly non-trivial work by ... more >>>

ISSN 1433-8092 | Imprint