On the NP-completeness of the logic puzzle irasuto

dc.rights.license	CC-BY-NC-ND
dc.contributor.advisor	Rin, Benjamin
dc.contributor.advisor	Caret, Colin
dc.contributor.author	Butter, S.Y.J.
dc.date.accessioned	2021-09-08T18:00:21Z
dc.date.available	2021-09-08T18:00:21Z
dc.date.issued	2021
dc.identifier.uri	https://studenttheses.uu.nl/handle/20.500.12932/1200
dc.description.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.
dc.description.sponsorship	Utrecht University
dc.format.extent	1597919
dc.format.mimetype	application/pdf
dc.language.iso	en
dc.title	On the NP-completeness of the logic puzzle irasuto
dc.type.content	Bachelor Thesis
dc.rights.accessrights	Open Access
dc.subject.keywords	NP; NP-complete; proof by reduction; gadgets; Planar Circuit SAT; pen-and-paper puzzle
dc.subject.courseuu	Kunstmatige Intelligentie