The complexity of short two-person games

DOI10.1016/0166-218X(90)90080-VzbMath0742.90089MaRDI QIDQ1173637

Ashok K. Chandra, Martin Tompa

Publication date: 25 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

\(P\)-completenesstwo-person games of perfect information

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) 2-person games (91A05) Turing machines and related notions (03D10)

Related Items (3)

A short certificate of the number of universal optimal strategies for stopping simple stochastic games ⋮ On the complexity of computational problems associated with simple stochastic games ⋮ The model checking fingerprints of CTL operators

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Speedups of deterministic machines by synchronous parallel machines
• Tree-size bounded alternation
• On uniform circuit complexity
• Properties that characterize LOGCFL
• On the complexity of some two-person perfect-information games
• Simulation of Parallel Random Access Machines by Circuits
• A taxonomy of problems with fast parallel algorithms
• A New Pebble Game that Characterizes Parallel Complexity Classes
• Alternation
• On the Tape Complexity of Deterministic Context-Free Languages

This page was built for publication: The complexity of short two-person games