Regular resolution lower bounds for the weak pigeonhole principle
type: Item
instance of: scholarly article
title: Regular resolution lower bounds for the weak pigeonhole principle
zbMATH Open document ID: 1063.03044
author: Toniann Pitassi
author: Ran Raz
published in: Combinatorica
publication date: 2005-07-05T00:00:00Z
review text: The paper is devoted to the study of the complexity of resolution proofs of the weak pigeonhole principle WPHP. It is shown that for any \(m\), any regular resolution proof for WPHP\(^{m}_{n}\) (i.e., weak pigeonhole principle with \(m\) pigeons and \(n\) holes) is of length \(\Omega (2^{n^{\epsilon}})\), where \(\epsilon > 0\) is some global constant.
reviewed by: Roman Murawski
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 2186328
zbMATH Keywords: weak pigeonhole principle
zbMATH Keywords: complexity of resolution proofs
MaRDI profile type: Publication
full work available at URL: s00493-004-0029-4
OpenAlex ID: W2001378190
DOI: 10.1007/S00493-004-0029-4
description: scientific article; zbMATH DE number 2186328