Computational Complexity of Puzzles and Related Topics

DOI Web Site 参考文献56件
  • UEHARA Ryuhei
    School of Information Science, Japan Advanced Institute of Science and Technology

抄録

<p>Since the 1930s, mathematicians and computer scientists have been interested in computation. While mathematicians investigate recursion theory, computer scientists investigate computational complexity based on Turing machine model to understand what a computation is. Beside them, there is another approach of research on computation, which is the investigation of puzzles and games. Once we regard the rules used in puzzles and games as the set of basic operations of computation, we can perform some computation by solving puzzles and playing games. In fact, research on puzzles and games from the viewpoint of theoretical computer science has continued without any break in the history of theoretical computer science. Sometimes the research on computational complexity classes has proceeded by understanding the tons of puzzles. The wide collection of complete problems for a specific computational complexity class shares a common property, which gives us a deep understanding of the class. In this survey paper, we give a brief history of research on computational complexities of puzzles and games with related results and trends in theoretical computer science.</p>

収録刊行物

参考文献 (56)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ