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

Conditional generative models for learning stochastic processes

Salvatore Certo, Anh Pham, et al.

Quantum Machine Intelligence

Conference paper

Single-shot General Hyper-parameter Optimization for Federated Learning

Yi Zhou, Parikshit Ram, et al.

ICLR 2023

Paper

Can one always lower topological entropy?

M. Shub, B. Weiss

Ergodic Theory and Dynamical Systems

Conference paper

Single and dual wavelength exposure of photoresist

J. LaRue, C. Ting

Proceedings of SPIE 1989

View all publications

Abstract

Related

Conditional generative models for learning stochastic processes

Single-shot General Hyper-parameter Optimization for Federated Learning

Can one always lower topological entropy?

Single and dual wavelength exposure of photoresist