Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Carsten Sinz:

TR09-087 | 1st October 2009
Olga Tveretina, Carsten Sinz, Hans Zantema

Ordered Binary Decision Diagrams, Pigeonhole Formulas and Beyond

Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula has an exponential
size and that limited OBDD derivations cannot simulate resolution polynomially. Here we show that any arbitrary OBDD Apply refutation of the pigeonhole formula has an exponential
size: we prove that the size of one ... more >>>

ISSN 1433-8092 | Imprint