The NP-completeness of pen and paper puzzles
Files
Publication date
Authors
DOI
Document Type
Bachelor Thesis
Metadata
Show full item recordCollections
License
CC-BY-NC-ND
Abstract
Pen and paper puzzles are often NP-complete. When a problem is NP-complete, it is commonly understood that (under the assumption that P is not equal to NP) the problem is too complex for computers to compute a solution in reasonable time. In this paper we use the Hamiltonian grid graph problem and Planar NOR CircuitSAT to prove that respectively Arukone3 and Bariasensa are NP-complete.
Keywords
NP-completeness, computational complexity, puzzles