NP-kovuus
NP-vaikea ongelma on kyllä/ei-ongelma, jonka ratkaiseminen on vähintään yhtä vaikeaa kuin sellaisen vaikeimman ongelman ratkaiseminen, jonka ratkaisu voidaan nopeasti tarkistaa todeksi. Osa NP-kovista ongelmista on sellaisia, joiden toimivan ratkaisun voi tarkistaa nopeasti (NP-ongelmat) ja osa ei. NP-vaikeat ongelmat, jotka ovat myös NP-ongelmia, kuuluvat luokkaan, jota kutsutaan NP-täydelliseksi.
Esimerkki ongelmasta, joka on vähintään yhtä vaikea ratkaista kuin mikä tahansa muu ongelma, jonka ratkaisut voimme tarkistaa nopeasti ja joka on myös nopeasti tarkistettavissa (se on sekä NP-kova että 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 vastaukset, mutta jos löydetään ratkaisu, jonka avulla myyjä voi tehdä tämän, voimme algoritmin avulla tarkistaa, että se on totta. Tämä ongelma tunnetaan myös nimellä Travelling salesman problem.
Esimerkki ongelmasta, joka on vähintään yhtä vaikea ratkaista kuin mikä tahansa muu ongelma, jonka ratkaisut voidaan tarkistaa nopeasti, mutta jota ei voida tarkistaa nopeasti (se on NP-vaikea, mutta se ei ole NP):
jos joku aloittaa ohjelman, joka yksinkertaisesti menee,
while(true){ continue; }eikä koskaan pysäytä sitä, toimiiko se ikuisesti?
Kaikkiin tämänkaltaisiin ongelmiin ei tunneta ratkaisua, eikä sitä voida myöskään tarkistaa.
Kysymyksiä ja vastauksia
Kysymys: Mikä on NP-vaikea ongelma?
V: NP-vaikea ongelma on tietotekniikassa käytetty matemaattisen ongelman tyyppi, joka on kyllä/ei-ongelma, jonka ratkaisun löytäminen on vähintään yhtä vaikeaa kuin sellaisen vaikeimman ongelman ratkaisun löytäminen, jonka ratkaisu voidaan nopeasti tarkistaa todeksi.
Kysymys: Voidaanko kaikille NP-koville ongelmille löytää nopeasti toimiva ratkaisu?
V: Ei, vain joidenkin NP-kovien ongelmien, joita kutsutaan NP-ongelmiksi, ratkaisut voidaan tarkistaa nopeasti.
K: Mikä on NP-kovien ongelmien, jotka ovat myös NP-ongelmia, kategoria?
V: NP-kovat ongelmat, jotka ovat myös NP-ongelmia, sopivat luokkaan nimeltä NP-täydellinen.
K: Ovatko kaikki NP-kovat ongelmat NP-täydellisiä?
V: Ei, kaikki NP-kovat ongelmat eivät ole NP-täydellisiä. Vain ne, jotka ovat myös NP-ongelmia, kuuluvat tähän luokkaan.
K: Ovatko NP-kovat ongelmat helppoja ratkaista?
V: Ei, NP-kovat ongelmat eivät ole helppoja ratkaista. Itse asiassa niiden ratkaisun löytäminen on vähintään yhtä vaikeaa kuin sellaisen vaikeimman ongelman ratkaisun löytäminen, jonka ratkaisu voidaan nopeasti tarkistaa todeksi.
K: Onko NP-kovien ongelmien ratkaisemisesta hyötyä?
V: Kyllä, NP-kovien ongelmien ratkaisemisesta voi olla hyötyä eri aloilla, kuten tietotekniikassa, fysiikassa ja yhteiskuntatieteissä, sillä ne voivat vaatia monimutkaisia laskutoimituksia ja mallintamista.
K: Onko NP-vaikeiden ongelmien ratkaisemiseen liittyvää tutkimusta käynnissä?
V: Kyllä, NP-vaikeiden ongelmien ratkaisemista tutkitaan jatkuvasti, koska nämä ongelmat ovat edelleen tärkeitä eri aloilla, ja tehokkaiden algoritmien ja ratkaisujen löytämisellä voi olla merkittäviä vaikutuksia.
