Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

DOI10.1016/J.TCS.2020.05.031MaRDI QIDQ2196563zbMATH OpenOpenAlexFDO

Authors Jeffrey Bosboom, Michael J. Coulombe, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy, Clemens Thielen, Zachary R. Abel

Publication date 3 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1721.1/128888

zbMATH Keywords

algorithmscomputational complexityHamiltonian pathhardnessvideo gamespath puzzles

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Games involving graphs (91A43)

Recommendations

• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
• NP-completeness of two pencil puzzles: Yajilin and Country Road
• The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake
• Tatamibari is NP-complete
• Computational complexity of NURIKABE

Cites work

• scientific article; zbMATH DE number 6381762 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7238987 (Why is no real title available?)
• Classic Nintendo games are (computationally) hard
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Drawing graphs on rectangular grids
• Edge-matching problems with rotations
• Fun with fonts: algorithmic typography
• Hamilton Paths in Grid Graphs
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• On Steiner’s Problem with Rectilinear Distance
• On the complexity of deadlock detection in families of planar nets
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• The Complexity of Planar Counting Problems
• The Problem of Compatible Representatives
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The undecidability of the domino problem
• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

Cited in

(1)

• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

This page was built for publication: Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196563)