Cops-robber games and the resolution of Tseitin formulas

DOI10.1007/978-3-319-94144-8_19zbMath1499.03054OpenAlexW2810331136MaRDI QIDQ1656588

Navid Talebanfard, Nicola Galesi, Jacobo Toran

Publication date: 10 August 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-94144-8_19

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24) Complexity of proofs (03F20) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (6)

Reversible pebble games and the relation between tree-like and general resolution space ⋮ On tseitin formulas, read-once branching programs and treewidth ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ Reflections on Proof Complexity and Counting Principles ⋮ Characterizing Tseitin-formulas with short regular resolution refutations

This page was built for publication: Cops-robber games and the resolution of Tseitin formulas