Mean-payoff games and propositional proofs
type: Item
instance of: scholarly article
title: Mean-payoff games and propositional proofs
zbMATH Open document ID: 1237.91043
author: Albert Atserias
author: Elitza Maneva
published in: Information and Computation
publication date: 2011-04-28T00:00:00Z
Mathematics Subject Classification ID: 91A24
Mathematics Subject Classification ID: 03B80
zbMATH DE Number: 5882202
zbMATH Keywords: mean-payoff games
zbMATH Keywords: proof complexity
zbMATH Keywords: resolution
zbMATH Keywords: Frege proof system
zbMATH Keywords: automatizability
zbMATH Keywords: feasible interpolation
MaRDI profile type: Publication
full work available at URL: j.ic.2011.01.003
OpenAlex ID: W1978132353
cites work: Resolution Is Not Automatizable Unless W[P] Is Tractable
cites work: On the automatizability of resolution and related propositional proof systems
cites work: Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
cites work: Mean-Payoff Games and Propositional Proofs
cites work: Q4399249
cites work: Short proofs are narrow—resolution made simple
cites work: The Max-Atom Problem and Its Relevance
cites work: Combinatorial structure and randomized subexponential algorithms for infinite games
cites work: Non-automatizability of bounded-depth Frege proofs
cites work: Lower bounds for cutting planes proofs with small coefficients
cites work: On Interpolation and Automatization for Frege Systems
cites work: Positional strategies for mean payoff games
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
cites work: A Deterministic Subexponential Algorithm for Solving Parity Games
cites work: A characterization of the minimum cycle mean in a digraph
cites work: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
cites work: Some consequences of cryptographical conjectures for \(S_2^1\) and EF
cites work: Matching theory
cites work: Scheduling with AND/OR Precedence Constraints
cites work: Q3221403
cites work: Lower bounds for resolution and cutting plane proofs and monotone computations
cites work: Q4215637
cites work: Q4934563
cites work: On reducibility and symmetry of disjoint NP pairs.
cites work: Q4375799
cites work: The complexity of mean payoff games on graphs
DOI: 10.1016/J.IC.2011.01.003
description: scientific article; zbMATH DE number 5882202