Graph expansion, Tseitin formulas and resolution proofs for CSP

DOI10.1007/978-3-642-38536-0_14MaRDI QIDQ4928481zbMATH OpenOpenAlexFDO

Authors Dmitry Itsykson, Vsevolod Oparin

Publication date 14 June 2013

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38536-0_14

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 176731
• Characterizing Tseitin-Formulas with Short Regular Resolution Refutations
• Tseitin's formulas revisited
• scientific article; zbMATH DE number 1361471
• Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs

Cited in

(10)

• Tseitin's formulas revisited
• Cops-robber games and the resolution of Tseitin formulas
• Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
• Bounded-depth Frege complexity of Tseitin formulas for all graphs
• Characterizing Tseitin-formulas with short regular resolution refutations
• scientific article; zbMATH DE number 176731 (Why is no real title available?)
• Cops-robber games and the resolution of Tseitin formulas
• Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
• On the resolution complexity of graph non-isomorphism
• Characterizing Tseitin-Formulas with Short Regular Resolution Refutations

This page was built for publication: Graph expansion, Tseitin formulas and resolution proofs for CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928481)