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

Self-assembling materials for lithographic patterning: Overview, status and moving forward

William Hinsberg, Joy Cheng, et al.

SPIE Advanced Lithography 2010

Paper

Bonsai trees, or how to delegate a lattice basis

David Cash, Dennis Hofheinz, et al.

Journal of Cryptology

Paper

Interactive scheduling as a constraint satisfiability problem

Ronen Feldman, Martin Charles Golumbic

Ann. Math. Artif. Intell.

Conference paper

On a partial ordering relation derived from redundancy of Slepian-Wolf coding

Da-Ke He, Ashish Jagmohan, et al.

ISIT 2007

View all publications

Abstract

Related

Self-assembling materials for lithographic patterning: Overview, status and moving forward

Bonsai trees, or how to delegate a lattice basis

Interactive scheduling as a constraint satisfiability problem

On a partial ordering relation derived from redundancy of Slepian-Wolf coding