Show simple item record

dc.contributor.authorTveretina, Olga
dc.contributor.authorSinz, Carsten
dc.contributor.authorZantema, Hans
dc.contributor.editorMarkakis, Evangelos
dc.contributor.editorMilis, Ioannis
dc.date.accessioned2013-02-28T15:09:54Z
dc.date.available2013-02-28T15:09:54Z
dc.date.issued2009
dc.identifier.citationTveretina , O , Sinz , C & Zantema , H 2009 , An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas . in E Markakis & I Milis (eds) , Procs 4th Athens Colloquium on Algorithms and Complexity : ACAC 2009 . pp. 13-21 , 4th Athens Colloquium on Algorithms and Complexity , Athens , Greece , 20/08/09 . https://doi.org/10.4204/EPTCS.4
dc.identifier.citationconference
dc.identifier.urihttp://hdl.handle.net/2299/10123
dc.description.abstractHaken 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)en
dc.format.extent85811
dc.language.isoeng
dc.relation.ispartofProcs 4th Athens Colloquium on Algorithms and Complexity
dc.titleAn Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulasen
dc.contributor.institutionSchool of Physics, Engineering & Computer Science
rioxxterms.versionofrecord10.4204/EPTCS.4
rioxxterms.typeOther
herts.preservation.rarelyaccessedtrue


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record