文章基本信息

标题：On the Power of Imperfect Information
本地全文：下载
作者：Dietmar Berwanger ; Laurent Doyen
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：2
页码：73-82
DOI：10.4230/LIPIcs.FSTTCS.2008.1742
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We present a polynomial-time reduction from parity games with imperfect information to safety games with imperfect information. Similar reductions for games with perfect information typically increase the game size exponentially. Our construction avoids such a blow-up by using imperfect information to realise succinct counters which cover a range exponentially larger than their size. In particular, the reduction shows that the problem of solving imperfect-information games with safety conditions is \EXPTIME-complete.
关键词：Infinite games; imperfect information