The complexity of short two-person games

Ashok K. Chandra; Martin Tompa

doi:10.1016/0166-218X(90)90080-V

Discrete Applied Mathematics

Paper

01 Jan 1990

The complexity of short two-person games

View publication

Abstract

Cook posed the question of finding a natural problem that is complete for AC1. It is shown here that a certain two-person game of perfect information is such a problem. Variants of this game are shown to be complete for P and for LOGCFL. © 1990.

Workshop paper

On Quantum Algorithms for Random Walks in the Nonnegative Quarter Plane

Conference paper

Dither computing: a hybrid deterministic-stochastic computing framework

Workshop paper

General Probability in Coq

Conference paper

Finite-Time Convergence and Sample Complexity of Multi-Agent Actor-Critic Reinforcement Learning with Average Reward

View all publications

Abstract

Related

On Quantum Algorithms for Random Walks in the Nonnegative Quarter Plane

Dither computing: a hybrid deterministic-stochastic computing framework

General Probability in Coq

Finite-Time Convergence and Sample Complexity of Multi-Agent Actor-Critic Reinforcement Learning with Average Reward