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

Can hospitals afford digital storage for imagery?

W.F. Cody, H.M. Gladney, et al.

SPIE Medical Imaging 1994

Paper

Dynamic graph and polynomial chaos based models for contact tracing data analysis and optimal testing prescription

Shashanka Ubaru, Lior Horesh, et al.

Journal of Biomedical Informatics

Paper

Interactive scheduling as a constraint satisfiability problem

Ronen Feldman, Martin Charles Golumbic

Ann. Math. Artif. Intell.

Conference paper

Convergence properties of multi-dimensional stack filters

Peter Wendt

Electronic Imaging: Advanced Devices and Systems 1990

View all publications

Abstract

Related

Can hospitals afford digital storage for imagery?

Dynamic graph and polynomial chaos based models for contact tracing data analysis and optimal testing prescription

Interactive scheduling as a constraint satisfiability problem

Convergence properties of multi-dimensional stack filters