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

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

Vladimir Yanovski, Israel A. Wagner, et al.

Ann. Math. Artif. Intell.

Conference paper

Anomalous interface degradation of a-Si:H TFTs during LCD lifetime

Frank R. Libsch, Takatoshi Tsujimura

Active Matrix Liquid Crystal Displays Technology and Applications 1997

Conference paper

Lithographic characteristics of 193-nm resists imaged at 193 and 248 nm

Juliann Opitz, Robert D. Allen, et al.

Microlithography 1998

Conference paper

Bonding, interfacial effects and adhesion in dlc

A. Grill, B.S. Meyerson, et al.

Proceedings of SPIE 1989

View all publications

Abstract

Related

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

Anomalous interface degradation of a-Si:H TFTs during LCD lifetime

Lithographic characteristics of 193-nm resists imaged at 193 and 248 nm

Bonding, interfacial effects and adhesion in dlc