ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



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 implies that the most ... more >>>



ISSN 1433-8092 | Imprint