NP-kovuus (NP-vaikeus): määritelmä, esimerkit ja NP-täydellisyys

Selkeä opas NP-kovuudesta, NP-vaikeudesta ja NP-täydellisyydestä: määritelmät, havainnollistavat esimerkit (Travelling Salesman) ja mitä ratkaisemattomuus tarkoittaa käytännössä.

NP-vaikea (NP-hard) tarkoittaa yleensä päätösongelmaa tai yleisempää laskentatehtävää, joka on vähintään yhtä vaikea kuin mikä tahansa ongelma luokassa NP. Tarkemmin: ongelma L on NP-vaikea, jos jokaista NP-luokan ongelmaa L' voidaan muuntaa L:ään polynomiaikaisella monikertaisella vähennysmenetelmällä (many-one reduction). Tämä tarkoittaa, että jos osaisimme ratkaista L:n tehokkaasti (polynomiajassa), osaisimme ratkaista myös kaikki NP-ongelmat tehokkaasti. NP-vaikeisiin ongelmiin kuuluu sekä sellaisia ongelmia, joiden ratkaisut voidaan nopeasti tarkistaa (eli ne ovat myös NP-ongelmia), että sellaisia ongelmia, jotka eivät kuulu NP:hen esimerkiksi siksi, että ne ovat ratkaisemattomia tai eivät ole päätösongelmia.

Mitä NP ja NP-täydellisyys tarkoittavat?

NP (nondeterministic polynomial time) on luokka päätösongelmia, joiden positiiviset vastaukset voidaan todistaa ja tarkistaa deterministisellä koneella polynomiajassa, kun todistus (todisteketju eli sertifikaatti) annetaan. Toinen vastaava määritelmä on, että ne ovat ongelmia, jotka voidaan ratkaista nondeterministisellä Turing-koneella polynomiajassa.

NP-täydellinen (NP-complete) ongelma on ongelma, joka on sekä NP-vaikea että kuuluu luokkaan NP. Toisin sanoen se on vaikein mahdollinen ongelma NP:ssa: jos joku NP-täydellinen ongelma ratkeaa polynomiajassa, kaikki NP-ongelmat ratkeavat polynomiajassa (eli P = NP).

Formaalimpi määrittely

• NP-vaikea: Kieli L on NP-vaikea, jos jokainen L' ∈ NP on polynomiaikaisesti monikertaisesti vähennettävissä L:ään (L' ≤p L).
• NP-täydellinen: L on NP-täydellinen jos L ∈ NP ja L on NP-vaikea.

Esimerkkejä ja selityksiä

Esimerkki NP-täydellisestä ongelmasta (NP-kova ja lisäksi NP):

Matkamyyjä haluaa vierailla 100 kaupungissa ajamalla ja aloittaa ja lopettaa matkansa kotona. Hänellä on rajallinen bensiinivarasto, joten hän voi ajaa yhteensä vain 10 000 kilometriä. Hän haluaa tietää, pystyykö hän käymään kaikissa kaupungeissa ilman, että bensiini loppuu kesken.

Ihmiset eivät tiedä, miten ratkaista tämä ongelma nopeammin kuin testaamalla kaikki mahdolliset reitit tai käyttämällä älykkäitä heuristiikkoja, mutta jos löydetään ehdotus reitistä, joka täyttää vaatimuksen, voimme algoritmin avulla tarkistaa ratkaisun nopeasti. Tämä päätösversiona muotoiltu ongelma tunnetaan myös nimellä Travelling salesman problem (päätösversiona: onko olemassa reitti, jonka pituus ≤ k?). Päätösversiona TSP on NP-täydellinen.

Esimerkki ongelmasta, joka on NP-vaikea mutta ei kuulu NP:hen (eli sitä ei voi yleisesti tarkistaa nopeasti):

Ajatellaan yksinkertaista kysymystä: jos joku aloittaa ohjelman, joka suorittaa jatkuvasti seuraavaa silmukkaa, toimiiko se ikuisesti (eli pysähtyykö se koskaan)? Esimerkkiohjelma:

while(true){ continue; }

Tämänkaltaisen kysymyksen yleinen muoto on klassinen pysähtymisongelma (halting problem), joka on tunnetusti ratkaisematon eli epäpäätösongelma. Halting-probleemiä pidetään NP-vaikeana, koska monia NP-ongelmia voidaan muuntaa (polynomiaikaisesti) halting-kysymyksiksi: annetaan syötteenä esimerkiksi lauseke tai järjestelmä, ja rakennetaan ohjelma, joka pysähtyy täsmälleen silloin kun alkuperäinen ongelma on myönteinen. Koska pysähtymisongelma ei ole päätösongelma luonnollisella tavalla kuuluva NP:hen eikä ole päätettävissä, se on esimerkki ongelmasta, joka voi olla vähintään yhtä vaikea kuin mikä tahansa NP-ongelma mutta ei kuulu NP:hen.

Miksi eroilla on merkitystä?

• Jos joku löytää polynomiaikaisen algoritmin jollekin NP-täydelliselle ongelmalle, siitä seuraa, että P = NP — se on yksi tietojenkäsittelytieteen suurista avoimista ongelmista.
• Monet käytännön optimointi- ja kombinatoriset ongelmat ovat NP-vaikeita tai NP-täydellisiä. Tällöin käytännössä haetaan heuristiikkoja, likiarvoja, satunnaistettuja algoritmeja tai erikoistapauksia, joissa ongelma on ratkaistavissa tehokkaasti.
• On lisäksi olemassa väliin jääviä ongelmia (NP-intermediate), joiden olemassaolo seuraa Ladnerin lauseesta, jos P ≠ NP: nämä olisivat NP-ongelmia, jotka eivät ole P:ssä eivätkä NP-täydellisiä.

Lisätietoja ja muita esimerkkejä

• Tunnettu NP-täydellinen ongelma: SAT (kielteistettävyyden tarkistus – Cook–Levinin lause osoitti SAT:n NP-täydelliseksi).
• Lisää NP-täydellisiä ongelmia: Hamiltonin sykli, CLIQUE, Vertex Cover, 3-SAT, Subset Sum (päätösversiona) jne.
• Optimointi-ongelmat kuten TSP:n optimointiversio (lyhin Hamiltonin kierto) ovat yleensä NP-vaikeita mutta eivät välttämättä NP-luokassa, koska ne eivät ole päätösongelmia.
• Käytännön työkaluihin kuuluvat heuristiikat, kokonaislukolinjaukset, metaheuristiikat (esim. genetiset algoritmit) ja approximointialgoritmit; joillekin NP-vaikeille ongelmille on myös tehokkaita likiarvoalgoritmeja.

Yhteenveto

Lyhyesti: NP-vaikea tarkoittaa, että ongelma on vähintään yhtä vaikea kuin mikä tahansa NP-luokan ongelma (kaikki NP-ongelmat voidaan muuntaa siihen polynomiaikaisesti). Jos lisäksi ongelma kuuluu NP:hen, se on NP-täydellinen. Monet keskeiset laskentatehtävät ovat NP-vaikeita tai NP-täydellisiä, ja niiden teoreettinen vaikeus selittää, miksi käytännössä käytetään usein likiarvoja ja heuristiikkoja sen sijaan, että löydettäisiin aina täsmällinen optimiratkaisu suurille syötteille.

Kysymyksiä ja vastauksia

Kysymys: Mikä on NP-vaikea ongelma?

Kysymys: Voidaanko kaikille NP-koville ongelmille löytää nopeasti toimiva ratkaisu?

K: Mikä on NP-kovien ongelmien, jotka ovat myös NP-ongelmia, kategoria?

K: Ovatko kaikki NP-kovat ongelmat NP-täydellisiä?

K: Ovatko NP-kovat ongelmat helppoja ratkaista?

K: Onko NP-kovien ongelmien ratkaisemisesta hyötyä?

K: Onko NP-vaikeiden ongelmien ratkaisemiseen liittyvää tutkimusta käynnissä?

Hae kirjaimella