Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AUTOMATED THEOREM PROVING:
Reports tagged with Automated Theorem Proving:
TR00-005 | 17th January 2000
Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

#### Near-Optimal Separation of Treelike and General Resolution

We present the best known separation
between tree-like and general resolution, improving
on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}.
This is done by constructing a natural family of contradictions, of
size $n$, that have $O(n)$-size resolution
refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.
This result ... more >>>

ISSN 1433-8092 | Imprint