An exponential separation between the parity principle and the pigeonhole principle
type: Item
instance of: scholarly article
title: An exponential separation between the parity principle and the pigeonhole principle
zbMATH Open document ID: 0866.03029
DOI: 10.1016/0168-0072(96)83747-X
author: Paul Beame
author: Toniann Pitassi
published in: Annals of Pure and Applied Logic
publication date: 1996-11-25T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 933080
zbMATH Keywords: combinatorial parity principle
zbMATH Keywords: perfect matching
zbMATH Keywords: pigeonhole principle
zbMATH Keywords: Frege proofs
zbMATH Keywords: lower bound
zbMATH Keywords: search classes
zbMATH Keywords: oracle separations
MaRDI profile type: Publication
cites work: The complexity of the pigeonhole principle
cites work: Q4035300
cites work: Q4234077
cites work: Optimal bounds for decision problems on the CRCW PRAM
cites work: Q3794177
cites work: Polynomial size proofs of the propositional pigeonhole principle
cites work: The relative efficiency of propositional proof systems
cites work: The intractability of resolution
cites work: An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
cites work: Q4027186
cites work: Exponential lower bounds for the pigeonhole principle
cites work: Q3689182
cites work: Hard examples for resolution
full work available at URL: 0168-0072(96)83747-x
OpenAlex ID: W2035926913
description: scientific article; zbMATH DE number 933080