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

A minimal descriptor of an ancestral recombinations graph

Laxmi Parida, Pier F. Palamara, et al.

BMC Bioinformatics

Paper

On convex relaxations of quadrilinear terms

Sonia Cafieri, Jon Lee, et al.

Journal of Global Optimization

Paper

Efficient Heuristics for Orientation Metric and Euclidean Steiner Tree Problems *

Y.Y. Li, K.S. Leung, et al.

J Combin Optim

Paper

Automated search method for AFM and profilers

Michael Ray, Yves C. Martin

Proceedings of SPIE - The International Society for Optical Engineering

View all publications

Abstract

Related

A minimal descriptor of an ancestral recombinations graph

On convex relaxations of quadrilinear terms

Efficient Heuristics for Orientation Metric and Euclidean Steiner Tree Problems *

Automated search method for AFM and profilers