On the complexity of succinct zero-sum games
From MaRDI portal
Publication:1024660
DOI10.1007/s00037-008-0252-2zbMath1162.91302MaRDI QIDQ1024660
Russell Impagliazzo, Valentine Kabanets, Christopher Umans, Lance J. Fortnow
Publication date: 17 June 2009
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-008-0252-2
68Q32: Computational learning theory
91A05: 2-person games
03D15: Complexity of computation (including implicit computational complexity)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
The 1-versus-2 queries problem revisited, On zero error algorithms having oracle access to one query, On the Complexity of Equilibria Problems in Angel-Daemon Games, Arthur and Merlin as Oracles