Number of the records: 1
Cops-Robber games and the resolution of Tseitin formulas
- 1.0491873 - MÚ 2019 RIV CH eng C - Conference Paper (international conference)
Galesi, N. - Talebanfard, Navid - Torán, J.
Cops-Robber games and the resolution of Tseitin formulas.
Theory and Applications of Satisfiability Testing – SAT 2018. Cham: Springer, 2018 - (Beyersdorff, O.; Wintersteiger, C.), s. 311-326. Lecture Notes in Computer Science, 10929. ISBN 978-3-319-94143-1. ISSN 0302-9743.
[21st International Conference, SAT 2018. Oxford (GB), 09.07.2018-12.07.2018]
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : formal logic * computer circuits
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://link.springer.com/chapter/10.1007%2F978-3-319-94144-8_19
We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed in our game in order to catch a robber in it, we are able to exactly characterize the width, variable space and depth measures for the resolution of the Tseitin formula corresponding to that graph. We also give an exact game characterization of resolution variable space for any formula.
We show that our game can be played in a monotone way. This implies that the corresponding resolution measures on Tseitin formulas correspond exactly to those under the restriction of regular resolution.
Using our characterizations we improve the existing complexity bounds for Tseitin formulas showing that resolution width, depth and variable space coincide up to a logarithmic factor, and that variable space is bounded by the clause space times a logarithmic factor.
Permanent Link: http://hdl.handle.net/11104/0285479
File Download Size Commentary Version Access Talebanfard1.pdf 2 241 KB Publisher’s postprint require
Number of the records: 1