This is a collection of my favourite open problems in theoretical computer science; many of them are about the (unknown) computational complexity of known puzzle games and their variants. Some of them are picked from the great Q&A sites cstheory.stackexchange.com and cs.stackexchange.com. Some of them are probably easy to solve, some of them are probably as hard to solve as the famous P vs NP problem.
I’ll try to keep the list updated with the new results, if you have some comments or suggestions or if you pick one of them and solve it, please feel free to contact me.
UCSP #1: Node and edge deletion game (I call it “Bridges and Islands game”)? |
|
| Description: | This games came to my mind, while working on another one. The bridges and islands game is a 2 players perfect information game. Given an undirected graph $G$, at each turn each player removes an edge (bridge) or an isolated node (island) from the graph. The first player unable to move loses. |
| Problem: | What is the complexity of deciding if there is a winning strategy for player A? |
| Variants: | The game is a variant of NODE KAYLES [1] which is PSPACE complete, and EDGE KAYLES whose complexity is unknwon [1]. |
| Status: | OPEN |
| Notes: | If played on a path then deciding the winner is polynomial time solvable; see my post on cstheory.stackexchange.com. |
| Resources: | [1] Thomas J. Schaefer, “On the Complexity of Some Two-Person Perfect-Information Games” |
UCSP #2: Is Boulder Dash in NP? |
|
| Description: | Boulder Dash in an old arcade game in which protagonist must dig through caves collecting gems and diamonds and reach the exit within a time limit, while avoiding various types of dangerous creatures as well as obstacles like falling rocks and the constant danger of being crushed or trapped by an avalanche, or killed by an underground explosion. |
| Problem: | Deciding if a given $n \times n$ Boulder Dash level is solvable, is $\sf{NP}$-hard [1][2]; but is it in $\sf{NP}$, i.e. if a level is solvable does it always have a solution which can be represented by a string having polynomial size $O(n^k)$? |
| Variants: | |
| Status: | OPEN |
| Resources: | [1] Giovanni Viglietta: “Gaming Is a Hard Job, But Someone Has to Do It!”, FUN 2012: 357-367; [2] Marzio De Biasi: “Have fun with Boulder Dash”, www.nearly42.org |
| UCSP #: | |
| Description: | … |
| Problem: | … |
| Variants: | … |
| Status: | OPEN | SOLVED |
| Resources: | … |