An exponential lower bound on OBDD refutations for pigeonhole formulas

O. Tveretina, C. Sinz, H. Zantema

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (Scopus)
2 Downloads (Pure)

Samenvatting

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 at least $\Omega(1.025^n)$.
Originele taal-2Engels
TitelProceedings 4th Athens Colloquium on Algorithms and Complexity (ACAC 2009, Athens, Greece, August 20-21, 2009)
RedacteurenE. Markakis, I. Milis
Uitgeverijs.n.
Pagina's13-21
DOI's
StatusGepubliceerd - 2009

Publicatie series

NaamElectronic Proceedings in Theoretical Computer Science
Volume4
ISSN van geprinte versie2075-2180

Vingerafdruk

Duik in de onderzoeksthema's van 'An exponential lower bound on OBDD refutations for pigeonhole formulas'. Samen vormen ze een unieke vingerafdruk.

Citeer dit