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.

Paper

Output distribution of the burrows-wheeler transform

Karthik Visweswariah, Sanjeev Kulkarni, et al.

IEEE International Symposium on Information Theory - Proceedings

Paper

New omega results in a weighted divisor problem

James Lee Hafner

Journal of Number Theory

Paper

The classification of one-sided Markov chains

Jonathan Ashley, Brian Marcus, et al.

Ergodic Theory and Dynamical Systems

Conference paper

Growth and transport properties of multilayer superconducting films of Nd_1.83Ce_0.17CuO_x / YBa₂Cu₃O_7-δ

A. Gupta, R. Gross, et al.

SPIE Advances in Semiconductors and Superconductors 1990

View all publications

Abstract

Related

Output distribution of the burrows-wheeler transform

New omega results in a weighted divisor problem

The classification of one-sided Markov chains

Growth and transport properties of multilayer superconducting films of Nd1.83Ce0.17CuOx / YBa2Cu3O7-δ

Growth and transport properties of multilayer superconducting films of Nd_1.83Ce_0.17CuO_x / YBa₂Cu₃O_7-δ