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 | |