Games against nature
type: Item
instance of: scholarly article
title: Games against nature
zbMATH Open document ID: 0583.68020
DOI: 10.1016/0022-0000(85)90045-5
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: We present a new characterization of PSPACE in terms of problems in a classical area in optimization, decision-making under uncertainty. These problems are modeled by certain games played against a disinterested opponent who makes moves at random. We show several natural problems of this sort to be PSPACE-complete.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 91A35
Mathematics Subject Classification ID: 91A80
zbMATH DE Number: 3934405
zbMATH Keywords: PSPACE
zbMATH Keywords: decision-making under uncertainty
zbMATH Keywords: games played against a disinterested opponent
Wikidata QID: Q30047574
author: Christos Papadimitriou
MaRDI profile type: Publication
full work available at URL: 0022-0000(85)90045-5
OpenAlex ID: W2019851160
cites work: Dynamic programming and stochastic control
cites work: Alternation
cites work: Q4138187
cites work: Q4427313
cites work: Q4198056
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Q3266141
cites work: Q4739657
cites work: On the complexity of some two-person perfect-information games
cites work: The polynomial-time hierarchy
cites work: The complexity of computing the permanent
cites work: Q4131987
description: scientific article; zbMATH DE number 3934405