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.

Conference paper

Super-resolution of Turbulent Flows in the Absence of the High-Resolution Ground Truth

Workshop paper

Topological Deep Learning

Poster

Uncovering signals of cell state transition using topological data analysis in single cell data

Conference paper

Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization

View all publications

Abstract

Related

Super-resolution of Turbulent Flows in the Absence of the High-Resolution Ground Truth

Topological Deep Learning

Uncovering signals of cell state transition using topological data analysis in single cell data

Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization