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

Bonsai trees, or how to delegate a lattice basis

David Cash, Dennis Hofheinz, et al.

Journal of Cryptology

Paper

A Formal Treatment of Non-repudiation Protocols

Satoshi Hada

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

Conference paper

Compression for data archiving and backup revisited

Corneliu Constantinescu

SPIE Optical Engineering + Applications 2009

Paper

Kinematic theory of signature verification measurements

John S. Lew

Mathematical Biosciences

View all publications

Abstract

Related

Bonsai trees, or how to delegate a lattice basis

A Formal Treatment of Non-repudiation Protocols

Compression for data archiving and backup revisited

Kinematic theory of signature verification measurements