Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs

From MaRDI portal
Publication:1983330

DOI10.1007/s00037-021-00213-2zbMath1497.03066OpenAlexW3198039724WikidataQ113906241 ScholiaQ113906241MaRDI QIDQ1983330

Danil Sagunov, Petr Smirnov, Artur Riazanov, Dmitry Itsykson

Publication date: 10 September 2021

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-021-00213-2




Related Items (4)



Cites Work


This page was built for publication: Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs