Who witnesses the witness? Finding witnesses in the witness is hard and sometimes impossible
We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw a path in a rectangular grid graph from a start vertex to a destination vertex. The different puzzle types place differe...
| Main Authors: | , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Dagstuhl Research
2020
|
| Online Access: | https://hdl.handle.net/1721.1/128888 |
| _version_ | 1811081855262261248 |
|---|---|
| author | Abel, Zachary R Bosboom, Jeffrey William Demaine, Erik D Hamilton, Linus Ulysses Hesterberg, Adam Classen Kopinsky, Justin Lynch, Jayson R. Rudoy, Mikhail |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Abel, Zachary R Bosboom, Jeffrey William Demaine, Erik D Hamilton, Linus Ulysses Hesterberg, Adam Classen Kopinsky, Justin Lynch, Jayson R. Rudoy, Mikhail |
| author_sort | Abel, Zachary R |
| collection | MIT |
| description | We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw a path in a rectangular grid graph from a start vertex to a destination vertex. The different puzzle types place different constraints on the path: preventing some edges from being visited (broken edges); forcing some edges or vertices to be visited (hexagons); forcing some cells to have certain numbers of incident path edges (triangles); or forcing the regions formed by the path to be partially monochromatic (squares), have exactly two special cells (stars), or be singly covered by given shapes (polyominoes) and/or negatively counting shapes (antipolyominoes). We show that any one of these clue types (except the first) is enough to make path finding NP-complete ("witnesses exist but are hard to find"), even for rectangular boards. Furthermore, we show that a final clue type (antibody), which necessarily "cancels" the effect of another clue in the same region, makes path finding Σ2-complete ("witnesses do not exist"), even with a single antibody (combined with many anti/polyominoes), and the problem gets no harder with many antibodies. |
| first_indexed | 2024-09-23T11:53:32Z |
| format | Article |
| id | mit-1721.1/128888 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:53:32Z |
| publishDate | 2020 |
| publisher | Dagstuhl Research |
| record_format | dspace |
| spelling | mit-1721.1/1288882022-10-01T06:45:50Z Who witnesses the witness? Finding witnesses in the witness is hard and sometimes impossible Abel, Zachary R Bosboom, Jeffrey William Demaine, Erik D Hamilton, Linus Ulysses Hesterberg, Adam Classen Kopinsky, Justin Lynch, Jayson R. Rudoy, Mikhail Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Mathematics We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw a path in a rectangular grid graph from a start vertex to a destination vertex. The different puzzle types place different constraints on the path: preventing some edges from being visited (broken edges); forcing some edges or vertices to be visited (hexagons); forcing some cells to have certain numbers of incident path edges (triangles); or forcing the regions formed by the path to be partially monochromatic (squares), have exactly two special cells (stars), or be singly covered by given shapes (polyominoes) and/or negatively counting shapes (antipolyominoes). We show that any one of these clue types (except the first) is enough to make path finding NP-complete ("witnesses exist but are hard to find"), even for rectangular boards. Furthermore, we show that a final clue type (antibody), which necessarily "cancels" the effect of another clue in the same region, makes path finding Σ2-complete ("witnesses do not exist"), even with a single antibody (combined with many anti/polyominoes), and the problem gets no harder with many antibodies. 2020-12-21T22:50:00Z 2020-12-21T22:50:00Z 2018 2019-06-05T12:57:00Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/128888 Abel, Zachary et al. "Who witnesses the witness? Finding witnesses in the witness is hard and sometimes impossible." 9th International Conference on Fun with Algorithms, June 2018, La Maddalena, Maddalena Islands, Italy, Dagstuhl Research, 2018. © 2018 The Authors en http://dx.doi.org/10.4230/LIPIcs.FUN.2018.3 9th International Conference on Fun with Algorithms Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Dagstuhl Research DROPS |
| spellingShingle | Abel, Zachary R Bosboom, Jeffrey William Demaine, Erik D Hamilton, Linus Ulysses Hesterberg, Adam Classen Kopinsky, Justin Lynch, Jayson R. Rudoy, Mikhail Who witnesses the witness? Finding witnesses in the witness is hard and sometimes impossible |
| title | Who witnesses the witness? Finding witnesses in the witness is hard and sometimes impossible |
| title_full | Who witnesses the witness? Finding witnesses in the witness is hard and sometimes impossible |
| title_fullStr | Who witnesses the witness? Finding witnesses in the witness is hard and sometimes impossible |
| title_full_unstemmed | Who witnesses the witness? Finding witnesses in the witness is hard and sometimes impossible |
| title_short | Who witnesses the witness? Finding witnesses in the witness is hard and sometimes impossible |
| title_sort | who witnesses the witness finding witnesses in the witness is hard and sometimes impossible |
| url | https://hdl.handle.net/1721.1/128888 |
| work_keys_str_mv | AT abelzacharyr whowitnessesthewitnessfindingwitnessesinthewitnessishardandsometimesimpossible AT bosboomjeffreywilliam whowitnessesthewitnessfindingwitnessesinthewitnessishardandsometimesimpossible AT demaineerikd whowitnessesthewitnessfindingwitnessesinthewitnessishardandsometimesimpossible AT hamiltonlinusulysses whowitnessesthewitnessfindingwitnessesinthewitnessishardandsometimesimpossible AT hesterbergadamclassen whowitnessesthewitnessfindingwitnessesinthewitnessishardandsometimesimpossible AT kopinskyjustin whowitnessesthewitnessfindingwitnessesinthewitnessishardandsometimesimpossible AT lynchjaysonr whowitnessesthewitnessfindingwitnessesinthewitnessishardandsometimesimpossible AT rudoymikhail whowitnessesthewitnessfindingwitnessesinthewitnessishardandsometimesimpossible |