dc.contributor.author | Tveretina, Olga | |
dc.contributor.author | Sinz, Carsten | |
dc.contributor.author | Zantema, Hans | |
dc.contributor.editor | Markakis, Evangelos | |
dc.contributor.editor | Milis, Ioannis | |
dc.date.accessioned | 2013-02-28T15:09:54Z | |
dc.date.available | 2013-02-28T15:09:54Z | |
dc.date.issued | 2009 | |
dc.identifier.citation | Tveretina , 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.citation | conference | |
dc.identifier.uri | http://hdl.handle.net/2299/10123 | |
dc.description.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) | en |
dc.format.extent | 85811 | |
dc.language.iso | eng | |
dc.relation.ispartof | Procs 4th Athens Colloquium on Algorithms and Complexity | |
dc.title | An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas | en |
dc.contributor.institution | School of Physics, Engineering & Computer Science | |
rioxxterms.versionofrecord | 10.4204/EPTCS.4 | |
rioxxterms.type | Other | |
herts.preservation.rarelyaccessed | true | |