Parameterized proof complexity
From MaRDI portal
Publication:451111
DOI10.1007/S00037-010-0001-1zbMATH Open1252.68151OpenAlexW2112145019MaRDI QIDQ451111FDOQ451111
Stefan Szeider, Stephan Stoyanov Danchev, Barnaby Martin
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
Recommendations
Cites Work
- Title not available (Why is that?)
- Which problems have strongly exponential complexity?
- Title not available (Why is that?)
- The relative efficiency of propositional proof systems
- Title not available (Why is that?)
- Improved Parameterized Upper Bounds for Vertex Cover
- The Turing way to parameterized complexity
- A complexity gap for tree resolution
- Proofs as Games
- Title not available (Why is that?)
Cited In (14)
- Parameterized Complexity of DPLL Search Procedures
- A Parameterized Halting Problem
- The power of parameterization in coinductive proof
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- Title not available (Why is that?)
- Parameterized Complexity Classes under Logical Reductions
- Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
- The complexity of proving that a graph is Ramsey
- Strong intractability results for generalized convex recoloring problems
- The Turing way to parameterized complexity
- Proof-Relevant Parametricity
- Parameterized Bounded-Depth Frege Is Not Optimal
- Strong intractability of generalized convex recoloring problems
- Relativization makes contradictions harder for resolution
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)
