Parity games and propositional proofs

0422131 - MÚ 2014 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Beckmann, A. - Pudlák, Pavel - Thapen, Neil
Parity games and propositional proofs.
Mathematical Foundations of Computer Science 2013. Berlin: Springer, 2013 - (Chatterjee, K.; Sgall, J.), s. 111-122. Lecture Notes in Computer Science, 8087. ISBN 978-3-642-40312-5.
[International Symposium on Mathematical Foundations of Computer Science 2013 /38./. Klosterneuburg (AT), 26.08.2013-30.08.2013]
Grant CEP: GA AV ČR IAA100190902
Institucionální podpora: RVO:67985840
Klíčová slova: resolution proof systems * parity games * game equivalent to resolution
Kód oboru RIV: BA - Obecná matematika
http://link.springer.com/chapter/10.1007%2F978-3-642-40313-2_12

A propositional proof system is weakly automatizable if there is a polynomial time algorithm which separates satisfiable formulas from formulas which have a short refutation in the system, with respect to a given length bound. We show that if the resolution proof system is weakly automatizable, then parity games can be decided in polynomial time. We also define a combinatorial game and prove that resolution is weakly automatizable if and only if one can separate, by a set decidable in polynomial time, the games in which the first player has a positional winning strategy from the games in which the second player has a positional winning strategy.
Trvalý link: http://hdl.handle.net/11104/0228345