Graph expansion, Tseitin formulas and resolution proofs for CSP

DOI10.1007/978-3-642-38536-0_14zbMATH Open1381.68098OpenAlexW114391025MaRDI QIDQ4928481FDOQ4928481

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

Recommendations

• scientific article
• 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

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)

Cited In (7)

• Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
• Tseitin's formulas revisited
• Characterizing Tseitin-formulas with short regular resolution refutations
• Title not available (Why is that?)
• Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
• Characterizing Tseitin-Formulas with Short Regular Resolution Refutations
• Bounded-depth Frege complexity of Tseitin formulas for all graphs

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)