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

Regression Optimization For System-level Production Control

Workshop paper

Nonconvex Min-Max Bilevel Optimization for Task Robust Meta Learning

Conference paper

Understanding latent correlation-based multiview learning and self-supervision: An identifiability perspective

Poster

Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity

View all publications

Abstract

Related

Regression Optimization For System-level Production Control

Nonconvex Min-Max Bilevel Optimization for Task Robust Meta Learning

Understanding latent correlation-based multiview learning and self-supervision: An identifiability perspective

Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity