Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALMOST-UNIVERSAL HASHING:
Reports tagged with almost-universal hashing:
TR07-126 | 5th November 2007
Nathan Segerlind

#### On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs

We show that tree-like OBDD proofs of unsatisfiability require an exponential increase ($s \mapsto 2^{s^{\Omega(1)}}$) in proof size to simulate unrestricted resolution, and that unrestricted OBDD proofs of unsatisfiability require an almost-exponential increase ($s \mapsto 2^{ 2^{\left( \log s \right)^{\Omega(1)}}}$) in proof size to simulate $\Res{O(\log n)}$. The OBDD proof ... more >>>

ISSN 1433-8092 | Imprint