Author | Conference | Journal | Organization | Year | DOI
Look for results that meet for the following criteria:
Academic
Publications
Mean-payoff games and propositional proofs

Mean-payoff games and propositional proofs,10.1016/j.ic.2011.01.003,Information and Computation/information and Control,Albert Atserias,Elitza N. Mane

Edit
Mean-payoff games and propositional proofs   (Citations: 1)
BibTex | RIS | RefWorks Download
We associate a CNF-formula to every instance of the mean-payoff game problem in such a way that if the value of the game is non-negative the formula is satisfiable, and if the value of the game is negative the formula has a polynomial-size refutation in Σ2-Frege (i.e. DNF-resolution). This reduces mean-payoff games to the weak automatizability of Σ2-Frege, and to the interpolation problem for Σ2,2-Frege. Since the interpolation problem for Σ1-Frege (i.e. resolution) is solvable in polynomial time, our result is close to optimal up to the computational complexity of solving mean-payoff games. The proof of the main result requires building low-depth formulas that compute the bits of the sum of a constant number of integers in binary notation, and low-complexity proofs of the required arithmetic properties.
Journal: Information and Computation/information and Control - IANDC , vol. 209, no. 4, pp. 664-691, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by:

Citations (1)

Share this on