University of Hertfordshire

By the same authors

An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Documents

  • 904837

    Accepted author manuscript, 83 KB, PDF document

View graph of relations
Original languageEnglish
Title of host publicationProcs 4th Athens Colloquium on Algorithms and Complexity
Subtitle of host publicationACAC 2009
EditorsEvangelos Markakis, Ioannis Milis
Pages13-21
DOIs
Publication statusPublished - 2009
Event4th Athens Colloquium on Algorithms and Complexity - Athens, Greece
Duration: 20 Aug 200921 Aug 2009

Conference

Conference4th Athens Colloquium on Algorithms and Complexity
CountryGreece
CityAthens
Period20/08/0921/08/09

Abstract

Haken proved that every resolution refutation of the pigeonhole formula has at least exponential size.
Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula has an exponential size. Here we show that any arbitrary OBDD refutation of the pigeonhole formula has an exponential size, too: we prove that the size of one of the intermediate OBDDs is W(1.025n)

ID: 1303031