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

DOI10.1016/J.TCS.2020.05.031zbMATH Open1453.68087OpenAlexW3037560582MaRDI QIDQ2196563FDOQ2196563

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

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

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)

Cites Work

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

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)