NP-täydellisyys peleissä

Abstract

Tässä työssä tarkastellaan sitä, mikä on NP-täydellisyys, miten se esiintyy peleissä sekä millaisia todistusmenetelmiä on käytetty esimerkkipelien NP-täydellisyyden todistuksissa. Työn tavoite on selventää NP-täydellisyyden käsitettä ja sen ilmenemistä pelien yhteydessä ensisijaisesti yliopistotason opiskelijoille, joiden opintoihin aiheen opiskelu sisältyy.

In this thesis we will go through what is NP-completeness and how does it show in games. The goal of this thesis is to clarify the concept of NP-completeness and its presence in games, primarily targeting university students, who are learning about the subject through their curriculum.