文献

J-GLOBAL ID：201802224579123077   整理番号：18A0263498

雪だるまはPSPACE完全である【Powered by NICT】

Snowman is PSPACE-complete

著者 (3件)： He Weihua (Department of Applied Mathematics, Guangdong University of Technology, Guangzhou, China) ,  Liu Ziwen (School of Software Engineering, South China University of Technology, Guangzhou, China) ,  Yang Chao (School of Mathematics, Sun Yat-Sen University, Guangzhou, China)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 677  ページ： 31-40  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 倉庫番は,文献で最も研究されているコンビナトリアルパズルゲームの一つである。1997年に初めてPSPACE完全であることが示されたその計算の複雑さ。この結果の新しい証明はearnおよびDemaine(2005)によって得られた,非決定性制約論理(Ncl)問題を導入した。それ以来,Nclは数倉庫番変異体を含むいくつかの他のパズルのPSPACE完全性を証明するために用い,多くの著者により調べた。本論文では,2015年に発表された新しい倉庫番のようなパズルゲーム,雪だるまであるNclからの還元によるPSPACE完全であることを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 完全性 ,  *倉庫 ,  計算量 ,  非決定性
準シソーラス用語： パズル , 【Automatic Indexing@JST】

著者キーワード (5件)： 組合せパズル ,  計算の複雑さ ,  PSPACE完全 ,  倉庫番 ,  非決定性制約論理

分類 (1件)： ゲーム理論  (KA03060T)