Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

**An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas.** / Tveretina, Olga; Sinz, Carsten; Zantema, Hans .

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

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) https://doi.org/10.4204/EPTCS.4

Tveretina O, Sinz C, Zantema H. An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas. In Markakis E, Milis I, editors, Procs 4th Athens Colloquium on Algorithms and Complexity: ACAC 2009. 2009. p. 13-21 https://doi.org/10.4204/EPTCS.4

@inproceedings{3f4aa0486fd243b7909c6623c0d12b58,

title = "An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas",

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) ",

author = "Olga Tveretina and Carsten Sinz and Hans Zantema",

year = "2009",

doi = "10.4204/EPTCS.4",

language = "English",

pages = "13--21",

editor = "Evangelos Markakis and Ioannis Milis",

booktitle = "Procs 4th Athens Colloquium on Algorithms and Complexity",

note = "4th Athens Colloquium on Algorithms and Complexity ; Conference date: 20-08-2009 Through 21-08-2009",

}

TY - GEN

T1 - An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas

AU - Tveretina, Olga

AU - Sinz, Carsten

AU - Zantema, Hans

PY - 2009

Y1 - 2009

N2 - 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)

AB - 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)

U2 - 10.4204/EPTCS.4

DO - 10.4204/EPTCS.4

M3 - Conference contribution

SP - 13

EP - 21

BT - Procs 4th Athens Colloquium on Algorithms and Complexity

A2 - Markakis, Evangelos

A2 - Milis, Ioannis

T2 - 4th Athens Colloquium on Algorithms and Complexity

Y2 - 20 August 2009 through 21 August 2009

ER -