Parameterized proof complexity

DOI10.1007/s00037-010-0001-1zbMath1252.68151OpenAlexW2112145019MaRDI QIDQ451111

Stefan Szeider, Barnaby Martin, Stefan S. Dantchev

Publication date: 21 September 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/4961/1/4961.pdf

zbMATH Keywords

parameterized complexitypropositional proof complexitycomplexity gap theorems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

Related Items (8)

A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games ⋮ Relativization makes contradictions harder for resolution ⋮ Strong intractability of generalized convex recoloring problems ⋮ Strong intractability results for generalized convex recoloring problems ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ The complexity of proving that a graph is Ramsey ⋮ Parameterized Bounded-Depth Frege Is Not Optimal ⋮ Parameterized Complexity of DPLL Search Procedures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A complexity gap for tree resolution
• Which problems have strongly exponential complexity?
• The Turing way to parameterized complexity
• Proofs as Games
• The relative efficiency of propositional proof systems
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: Parameterized proof complexity