Name
Abstract | ||
|---|---|---|
We study the computational complexity of the Buttons u0026 Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for (C=2) colors but polytime solvable for (C=1). Similarly the game is NP-complete if every color is used by at most (F=4) buttons but polytime solvable for (Fle 3). We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete. |
Year | Venue | Field |
|---|---|---|
2016 | Lecture Notes in Computer Science | Discrete mathematics,Computer science,Computational complexity theory |
DocType | Volume | Citations |
Journal | abs/1607.01826 | 0 |
PageRank | References | Authors |
0.34 | 4 | 15 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kyle Burke | 1 | 0 | 1.01 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Harrison Gregg | 3 | 0 | 1.01 |
| Robert A. Hearn | 4 | 169 | 20.52 |
| Adam Hesterberg | 5 | 4 | 7.07 |
| Michael Hoffmann | 6 | 227 | 22.74 |
| Hiro Ito | 7 | 290 | 39.95 |
| Irina Kostitsyna | 8 | 33 | 18.08 |
| Jody Leonard | 9 | 0 | 1.01 |
| Maarten Löffler | 10 | 551 | 62.87 |
| Aaron Santiago | 11 | 0 | 1.01 |
| Christiane Schmidt 0001 | 12 | 5 | 2.87 |
| Ryuhei Uehara | 13 | 528 | 75.38 |
| yushi uno | 14 | 222 | 28.80 |
| Aaron Williams | 15 | 139 | 20.42 |