The Library
The complexity of mean payoff games
Tools
UNSPECIFIED (1995) The complexity of mean payoff games. In: 1st Annual International Computing and Combinatorics Conference (COCOON 95), XIAN, PEOPLES R CHINA, AUG 24-26, 1995. Published in: COMPUTING AND COMBINATORICS, 959 pp. 1-10. ISBN 3-540-60216-X. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
We study the complexity of finding the values and optimal strategies of mean payoff games, a family of perfect information games introduced by Ehrenfeucht and Mycielski. We describe a pseudo-polynomial time algorithm for the solution of such games, the decision problem for which is in NP boolean AND co-NP. Finally, we describe a polynomial reduction from mean payoff games to the simple stochastic games studied by Condon. These games are also known to be in NP boolean AND co-NP, but no polynomial or pseudo-polynomial time algorithm is known for them.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | COMPUTING AND COMBINATORICS | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-60216-X | ||||
ISSN: | 0302-9743 | ||||
Editor: | Du, DZ and Li, M | ||||
Official Date: | 1995 | ||||
Dates: |
|
||||
Volume: | 959 | ||||
Number of Pages: | 10 | ||||
Page Range: | pp. 1-10 | ||||
Publication Status: | Published | ||||
Title of Event: | 1st Annual International Computing and Combinatorics Conference (COCOON 95) | ||||
Location of Event: | XIAN, PEOPLES R CHINA | ||||
Date(s) of Event: | AUG 24-26, 1995 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |