Games against nature

DOI10.1016/0022-0000(85)90045-5zbMath0583.68020WikidataQ30047574 ScholiaQ30047574MaRDI QIDQ1069296

Christos H. Papadimitriou

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(85)90045-5

zbMATH Keywords

decision-making under uncertainty; PSPACE; games played against a disinterested opponent

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91A80: Applications of game theory

91A35: Decision theory for games

Related Items

TETRIS IS HARD, EVEN TO APPROXIMATE, Challenges in Constraint-Based Analysis of Hybrid Systems, Stochastic Satisfiability Modulo Theories for Non-linear Arithmetic, Scheduling Two-Point Stochastic Jobs to Minimize the Makespan on Two Parallel Machines, Dot operators, Moving in a network under random failures: a complexity analysis, Constraint-based analysis of concurrent probabilistic hybrid systems: an application to networked automation systems, Randomization for robot tasks: using dynamic programming in the space of knowledge states, Engineering constraint solvers for automatic analysis of probabilistic hybrid automata, Shortest paths without a map, Contingent planning under uncertainty via stochastic satisfiability, Computation of equilibria in noncooperative games, Optimal node visitation in acyclic stochastic digraphs with multi-threaded traversals and internal visitation requirements, APPSSAT: Approximate probabilistic planning using stochastic satisfiability, An application of quantum finite automata to interactive proof systems, Minimum disclosure proofs of knowledge, Interactive foundations of computing, The complexity of stochastic games, Generalizations of Opt P to the polynomial hierarchy, A short certificate of the number of universal optimal strategies for stopping simple stochastic games, On the complexity of partially observed Markov decision processes, Sound and efficient closed-world reasoning for planning, Quantum multi-prover interactive proof systems with limited prior entanglement., Interactive and probabilistic proof-checking, Decision algorithms for multiplayer noncooperative games of incomplete information, Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete., Computational complexity of stochastic programming problems, Solving H-horizon, stationary Markov decision problems in time proportional to log (H), Unnamed Item, Generalized Craig Interpolation for Stochastic Boolean Satisfiability Problems, Scheduling Stochastic Jobs with a Two-Point Distribution on Two Parallel Machines, On the Relationship between Hybrid Probabilistic Logic Programs and Stochastic Satisfiability, De Groot duality and models of choice: angels, demons and nature, From State-of-the-Art Static Fleet Assignment to Flexible Stochastic Planning of the Future, The polynomial hierarchy and a simple model for competitive analysis, Classifying the computational complexity of problems

Cites Work

• The complexity of computing the permanent
• Dynamic programming and stochastic control
• The polynomial-time hierarchy
• On the complexity of some two-person perfect-information games
• Alternation
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Computational Complexity of Probabilistic Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item