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

Optimization of real phase-mask performance

F.M. Schellenberg, M. Levenson, et al.

BACUS Symposium on Photomask Technology and Management 1991

Paper

Airy stress function for atomic models

Paul J. Steinhardt, P. Chaudhari

Journal of Computational Physics

Paper

Multi-dimensional Filter Banks and Wavelets - A System Theoretic Perspective

Sankar Basu

Journal of the Franklin Institute

Paper

Vertex-Ant-Walk - A robust method for efficient exploration of faulty graphs

Vladimir Yanovski, Israel A. Wagner, et al.

Ann. Math. Artif. Intell.

View all publications

Abstract

Related

Optimization of real phase-mask performance

Airy stress function for atomic models

Multi-dimensional Filter Banks and Wavelets - A System Theoretic Perspective

Vertex-Ant-Walk - A robust method for efficient exploration of faulty graphs