On the NP-completeness of the logic puzzle irasuto
Publication date
Authors
DOI
Document Type
Bachelor Thesis
Metadata
Show full item recordCollections
License
CC-BY-NC-ND
Abstract
This thesis investigates the computational complexity of the Japanese pen-and-paper puzzle irasuto. We show that the problem is NP-complete by presenting a polynomial time reduction from Planar Circuit SAT containing only NOR gates to irasuto.
Keywords
NP; NP-complete; proof by reduction; gadgets; Planar Circuit SAT; pen-and-paper puzzle