Morris Lundberg Allerholm: Kakurasu is NP-complete

Abstract.

(English) NP-complete puzzle games demonstrate the intriguing complexity that can arise from the combination of simple rules, and allow for non-mathematicians to interface with one of the largest unsolved questions in mathematics: P versus NP. In this thesis, we introduce the concept of NP-completeness in the context of other, similar types of problems. We then show that the puzzle game Kakurasu is NP-complete.

(Svenska) NP-kompletta pusselspel visar på den fängslande komplexitet som kan uppstå genom kombinationen av enkla regler, och tillåter på så vis icke-matematiker att interagera med en av de största olösta frågorna inom matematiken: P kontra NP. I den här uppsatsen introducerar vi konceptet NP-kompletthet i kontext av andra, liknande problem. Vi visar sedan att pusselspelet Kakurasu är NP-komplett.