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

New omega results in a weighted divisor problem

James Lee Hafner

Journal of Number Theory

Conference paper

Effects of KrF laser radiation on fused-silica glass: a comparison of samples exposed in air vs vacuum

I.K. Pour, D.J. Krajnovich, et al.

SPIE Optical Materials for High Average Power Lasers 1992

Paper

Efficient Heuristics for Orientation Metric and Euclidean Steiner Tree Problems *

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

J Combin Optim

Paper

An information statistics approach to data stream and communication complexity

Ziv Bar-Yossef, T.S. Jayram, et al.

Journal of Computer and System Sciences

View all publications

Abstract

Related

New omega results in a weighted divisor problem

Effects of KrF laser radiation on fused-silica glass: a comparison of samples exposed in air vs vacuum

Efficient Heuristics for Orientation Metric and Euclidean Steiner Tree Problems *

An information statistics approach to data stream and communication complexity