We consider the proof system Res introduced by Itsykson and Sokolov (Ann. Pure Appl. Log.'20), which is an extension of the resolution proof system and operates with disjunctions of linear equations over .We study characterizations of tree-like size and space of Res refutations using combinatorial games. Namely, we introduce a class of extensible formulas and prove tree-like size lower bounds on it using Prover-Delayer games, as well as space lower bounds. This class is of particular interest since it contains many classical combinatorial principles, including the pigeonhole, ordering, and dense linear ordering principles. Furthermore, we present the width-space relation for Res generalizing the results by Atserias and Dalmau (J. Comput. Syst. Sci.'08) and their variant of Spoiler-Duplicator games. © 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.
Язык оригиналаАнглийский
Число страниц15
ЖурналACM Transactions on Computation Theory
Том16
Номер выпуска3
DOI
СостояниеОпубликовано - 30 сен 2024

ID: 126386676