A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
type: Item
instance of: scholarly article
title: A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
zbMATH Open document ID: 1379.03017
author: Olaf Beyersdorff
author: Nicola Galesi
author: Massimo Lauria
published in: Information Processing Letters
publication date: 2017-11-03T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03F07
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6802678
zbMATH Keywords: computational complexity
zbMATH Keywords: proof complexity
zbMATH Keywords: prover-delayer games
zbMATH Keywords: resolution
Wikidata QID: Q57949504
MaRDI profile type: Publication
full work available at URL: j.ipl.2010.09.007
OpenAlex ID: W2067510740
cites work: A combinatorial characterization of resolution width
cites work: Near optimal seperation of tree-like and general resolution
cites work: Parameterized proof complexity
cites work: On the complexity of resolution with bounded conjunctions
cites work: Q4511222
cites work: Q4856172
cites work: Q4474836
cites work: Q4952609
cites work: Q4934563
cites work: The Complexity of Propositional Proofs
DBLP publication ID: journals/ipl/BeyersdorffGL10
DOI: 10.1016/J.IPL.2010.09.007
description: scientific article; zbMATH DE number 6802678