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

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

zbMATH Keywords

parameterized complexitypropositional proof complexitycomplexity gap theorems

Mathematics Subject Classification ID

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

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 (20)

• Some definitorial suggestions for parameterized proof complexity
• 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 provability in equational logic
• Parameterized bounded-depth Frege is not optimal
• Parameterized complexity of DPLL search procedures
• Parameterized resolution with bounded conjunction
• Parameterized Complexity Classes under Logical Reductions
• Relativization and interactive proof systems in parameterized complexity theory
• Parameterized bounded-depth Frege is not optimal
• 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
• Strong intractability of generalized convex recoloring problems
• Relativization makes contradictions harder for resolution
• Some lower bounds in parameterized \(\mathrm{AC}^0\)

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)