Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-332 | 21st November 2026 22:17

Resolution Is Automatable on Tseitin Formulas

RSS-Feed




TR26-332
Authors: Dmitry Itsykson, Petr Smirnov
Publication: 22nd November 2026 15:35
Downloads: 21
Keywords: 


Abstract:

We prove that both regular and unrestricted resolution are automatable on Tseitin formulas, resolving a question of Alekhnovich and Razborov (Comput. Complex. 2011). We use known proof-search algorithms that apply to arbitrary CNFs and are parameterized by the treewidth of the primal graph. Our lower bounds show that these algorithms suffice to find a regular refutation of any Tseitin contradiction in time polynomial in the input length and the length of a shortest unrestricted refutation. We also establish a polynomial equivalence between regular and unrestricted resolution on Tseitin formulas, proving a weaker version of Urquhart's conjecture that their minimum regular and unrestricted resolution refutation lengths are equal.

Our main technical results are unrestricted resolution lower bounds of $2^{\Omega(tw(G))}$ for Tseitin contradictions on arbitrary connected graphs $G$, and $2^{\Omega(tw(L(G)))}$ when $G$ additionally has no bridges, where $L(G)$ is the line graph of $G$. The first bound combines the Ben-Sasson--Wigderson measure argument with random restrictions based on a distribution on spanning trees. The second follows from a reduction to bounded-degree graphs that replaces vertices with expander gadgets.



ISSN 1433-8092 | Imprint