A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games

DOI10.1016/j.ipl.2010.09.007zbMath1379.03017DBLPjournals/ipl/BeyersdorffGL10OpenAlexW2067510740WikidataQ57949504 ScholiaQ57949504MaRDI QIDQ1675824

Nicola Galesi, Olaf Beyersdorff, Massimo Lauria

Publication date: 3 November 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.09.007

zbMATH Keywords

computational complexityresolutionproof complexityprover-delayer games

Mathematics Subject Classification ID

Structure of proofs (03F07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (11)

A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games ⋮ Relativization makes contradictions harder for resolution ⋮ A game characterisation of tree-like Q-resolution size ⋮ A characterization of tree-like resolution size ⋮ Unnamed Item ⋮ A Game Characterisation of Tree-like Q-resolution Size ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ A Tutorial on Time and Space Bounds in Tree-Like Resolution ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs

Cites Work

• Parameterized proof complexity
• Near optimal seperation of tree-like and general resolution
• A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
• On the complexity of resolution with bounded conjunctions
• A combinatorial characterization of resolution width
• The Complexity of Propositional Proofs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games