Mean-payoff games and propositional proofs

DOI10.1016/j.ic.2011.01.003zbMath1237.91043OpenAlexW1978132353MaRDI QIDQ716324

Albert Atserias, Elitza Maneva

Publication date: 28 April 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2011.01.003

zbMATH Keywords

resolutionproof complexityautomatizabilitymean-payoff gamesfeasible interpolationFrege proof system

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24) Other applications of logic (03B80)

Related Items (4)

Tropically convex constraint satisfaction ⋮ Parity Games and Propositional Proofs ⋮ The canonical pairs of bounded depth Frege systems ⋮ Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Combinatorial structure and randomized subexponential algorithms for infinite games
• Matching theory
• Positional strategies for mean payoff games
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• On reducibility and symmetry of disjoint NP pairs.
• Non-automatizability of bounded-depth Frege proofs
• Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
• On the automatizability of resolution and related propositional proof systems
• Parity, circuits, and the polynomial-time hierarchy
• Resolution Is Not Automatizable Unless W[P Is Tractable]
• A Deterministic Subexponential Algorithm for Solving Parity Games
• Mean-Payoff Games and Propositional Proofs
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Short proofs are narrow—resolution made simple
• On Interpolation and Automatization for Frege Systems
• Scheduling with AND/OR Precedence Constraints
• The Max-Atom Problem and Its Relevance

This page was built for publication: Mean-payoff games and propositional proofs