Parameterized proof complexity

DOI10.1007/S00037-010-0001-1zbMATH Open1252.68151OpenAlexW2112145019MaRDI QIDQ451111FDOQ451111

Authors Barnaby Martin, Stefan Szeider, Stephan Stoyanov Danchev 

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)

Recommendations

• Parameterized bounded-depth Frege is not optimal
• Parameterized bounded-depth Frege is not optimal
• Some definitorial suggestions for parameterized proof complexity
• Parameterized complexity of constraint satisfaction problems
• On finding short resolution refutations and small unsatisfiable subsets

Cites work

• scientific article; zbMATH DE number 1223618 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A complexity gap for tree resolution
• Improved Parameterized Upper Bounds for Vertex Cover
• Proofs as Games
• The Turing way to parameterized complexity
• The relative efficiency of propositional proof systems
• Which problems have strongly exponential complexity?

Cited in

(19)

• Strong intractability results for generalized convex recoloring problems
• The Turing way to parameterized complexity
• Strong intractability of generalized convex recoloring problems
• Parameterized resolution with bounded conjunction
• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
• Some definitorial suggestions for parameterized proof complexity
• Relativization and interactive proof systems in parameterized complexity theory
• Proof-Relevant Parametricity
• Parameterized Complexity Classes under Logical Reductions
• A Parameterized Halting Problem
• scientific article; zbMATH DE number 2212138 (Why is no real title available?)
• The power of parameterization in coinductive proof
• Relativization makes contradictions harder for resolution
• Parameterized provability in equational logic
• Parameterized bounded-depth Frege is not optimal
• Some lower bounds in parameterized \(\mathrm{AC}^0\)
• Parameterized bounded-depth Frege is not optimal
• Parameterized complexity of DPLL search procedures
• A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games

This page was built for publication: Parameterized proof complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q451111)