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

Automated search method for AFM and profilers

Michael Ray, Yves C. Martin

Proceedings of SPIE - The International Society for Optical Engineering

Conference paper

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

William Hinsberg, Joy Cheng, et al.

SPIE Advanced Lithography 2010

Paper

Mapping behavioral specifications to model parameters in synthetic biology

Heinz Koeppl, Marc Hafner, et al.

BMC Bioinformatics

Paper

A Formal Treatment of Non-repudiation Protocols

Satoshi Hada

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

View all publications

Abstract

Related

Automated search method for AFM and profilers

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

Mapping behavioral specifications to model parameters in synthetic biology

A Formal Treatment of Non-repudiation Protocols