NP-monimutkaisuuden ymmärtäminen: määritelmä ja esimerkkejä

NP on lyhenne sanoista "ei-deterministinen polynomiaika". Se on monimutkaisuusluokka, joka viittaa ongelman ratkaisemiseen tarvittavaan aikaan. NP:ssä algoritmin käyntiaika voi olla polynomi syötteen koon suhteen, mutta se voi olla myös epädeterministinen, mikä tarkoittaa, että käyntiaika voi vaihdella algoritmin valitseman ratkaisun mukaan. Toisin sanoen NP on luokka ongelmia, jotka voidaan ratkaista polynomiajassa epädeterministisellä koneella. Epädeterministinen kone on kone, joka voi kokeilla kaikkia mahdollisia ratkaisuja ongelmaan rinnakkain ja hyväksyä ensimmäisen toimivan. Tämän ansiosta kone pystyy ratkaisemaan jotkin ongelmat paljon nopeammin kuin deterministinen kone, joka voi yrittää vain yhtä ratkaisua kerrallaan.

Joitakin esimerkkejä NP:n ongelmista ovat:

* Matkustajamyyjän ongelma (jos on luettelo kaupungeista ja niiden parittaiset etäisyydet, löytää lyhin mahdollinen reitti, joka vierailee kussakin kaupungissa täsmälleen kerran)
* Reppu-ongelma (kun otetaan huomioon kohteiden joukko ja niiden painot ja arvot, määritä tavaroiden osajoukko, joka sisällytetään rajoitetun kapasiteetin reppuun, joka maksimoi kokonaisarvon)
* Boolen tyydyttävyysongelma (kun otetaan huomioon joukko loogisia muuttujia ja niiden rajoituksia, määritetään, onko muuttujille annettu arvot, jotka täyttävät kaikki rajoitukset)

NP-kompleksisuusluokka on tärkeä, koska se sisältää monia ongelmia, joita on vaikea ratkaista polynomissa aika, mutta se voidaan varmistaa nopeasti deterministisellä koneella. Tämä tarkoittaa, että vaikka algoritmi ei ehkä pysty löytämään ratkaisua polynomiajassa, se voi silti olla hyödyllistä, jos se voi varmistaa ehdotetun ratkaisun nopeasti.