NPvaikeita

NP-vaikeita (engl. *NP-hard*) on tietotekniikassa ja matemaatikassa käytetty luokitus, joka kuvaa ongelmien vaikeusastetta. Luokkaan kuuluvat ongelmat ovat yleensä niin vaikeita, että niiden ratkaisemiseen ei tunneta tehokkaita algoritmeja, jotka toimisivat kaikissa tapauksissa suhteellisen lyhyessä ajassa. NP-vaikeita ongelmia esiintyy monilla aloilla, kuten optimointitehtävissä, graafiteorioissa ja kombinatoriikassa.

NP-vaikeiden ongelmien tunnistaminen on tärkeää, koska se auttaa ymmärtämään, milloin tietynlaiset ratkaisut ovat käytännössä mahdottomia suuren määrän vaihtoehtojen vuoksi. Esimerkiksi klassinen esimerkki on *traveling salesman problem* (myyjän matka-ongelma), jossa pyritään löytämään lyhin mahdollinen reitti, joka kulkee kaikkien tiettyjen kohteiden kautta kerran. Ongelman ratkaiseminen täydellisesti on NP-vaikeaa, vaikka sen yksinkertaisempia versioita voidaan ratkaista tehokkaasti.

NP-vaikeita ongelmia ei tule sekoittaa NP-ongelmiin, jotka ovat NP-vaikeiden osajoukko. NP-ongelmat ovat sellaisia, joiden ratkaisun oikeellisuutta voidaan tarkistaa tehokkaasti, vaikka niiden löytäminen itsessään voisi olla vaikeaa. NP-vaikeiden ongelmien ratkaiseminen on yleensä yhtä vaikeaa kuin NP-ongelmien ratkaiseminen, mutta niillä ei välttämättä ole samaa tarkistusominaisuutta.

Vaikka NP-vaikeiden ongelmien ratkaiseminen täydellisesti voi olla mahdotonta, niihin voidaan soveltaa approksimaatioalgoritmeja tai heuristisia menetelmiä, jotka tarjoavat lähellä optimaalisen ratkaisun suhteellisen lyhyessä ajassa. Näin ongelmat voivat silti olla käytännössä ratkaistavissa riippuen käytettävistä resursseista ja vaaditusta tarkkuudesta.