Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP

DOI10.1007/978-3-642-38536-0_14zbMath1381.68098OpenAlexW114391025MaRDI QIDQ4928481

Vsevolod Oparin, Dmitry Itsykson

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

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

Related Items (5)

Characterizing Tseitin-Formulas with Short Regular Resolution Refutations ⋮ 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 ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ Characterizing Tseitin-formulas with short regular resolution refutations

This page was built for publication: Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP