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

Standard

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

Procs 4th Athens Colloquium on Algorithms and Complexity: ACAC 2009. ed. / Evangelos Markakis; Ioannis Milis. 2009. p. 13-21.

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

Harvard

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

APA

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

Vancouver

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

Author

Tveretina, Olga ; Sinz, Carsten ; Zantema, Hans . / An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas. Procs 4th Athens Colloquium on Algorithms and Complexity: ACAC 2009. editor / Evangelos Markakis ; Ioannis Milis. 2009. pp. 13-21

Bibtex

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

}

RIS

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 -