@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00097526,
 author = {田中, 哲朗 and Tanaka, Tetsuro},
 book = {ゲームプログラミングワークショップ2002論文集},
 issue = {17},
 month = {Nov},
 note = {「しりとりゲーム」はしりとりを完全情報化して定義したゲームである．完全情報ゲームなので，使用可能な文字の種類，使用可能な単語の集合と開始文字を決めれば，勝敗は決定可能である．「しりとりゲーム」の勝敗に関してはグラフとして表現した時に勝敗が同じで辺の少ないグラフに簡約する方法，文字の種類をnとしたとき，n=3までは定数時間で勝敗を決定可能であることが分かっているが，nを増やしていったときに，効率的に勝敗を決定するアルゴリズムがあるかは分かっていなかった．本論文では，しりとりゲームの勝敗の決定問題が文字の種類nに対してNP困難であることを示した．これにより，文字の種類によらずに，しりとりゲームの勝敗を効率的に求めるプログラムを書くのが困難であることが分かる．, The word-chain game (SHIRITORI in Japanese) in which two players are assumed to know all the words can be modeled as a game on graph. When given a set of words with a word to start, it is theoretically possible to decide whether the first player can win the game or not because it is a game with perfect information. As the alphabet size become bigger, problems become more difficult. In this paper, we show that problem is NP-hard.},
 pages = {140--142},
 publisher = {情報処理学会},
 title = {しりとりゲームのNP困難性},
 volume = {2002},
 year = {2002}
}