NP (vaativuusluokka)

NP (nondeterministic polynomial) on laskennan vaativuusteoriassa vaativuusluokka, johon kuuluvat ongelmat voidaan tarkistaa deterministisellä Turingin koneella polynomisessa ajassa, eli "tehokkaasti". Yhtäpitävästi voidaan määritellä, että luokan NP ongelmat voidaan ratkaista epädeterministisellä Turingin koneella polynomisessa ajassa. Epädeterministinen Turingin kone voi tehdä monta asiaa yhtäaikaisesti vastauksena sen saamaan syötteeseen. Määritelmästä seuraa, että kaikki luokan P ongelmat ovat myös NP-ongelmia, sillä kaikki polynomisessa ajassa ratkaistavat ongelmat voidaan myös tarkistaa polynomisessa ajassa.

Kuuluisa ratkaisematon kysymys P=NP kysyy, ovatko vaativuusluokat P ja NP kuitenkin sama asia, eli voidaanko kaikki polynomisessa ajassa tarkastettavat ongelmat myös ratkaista polynomisessa ajassa. Monet ongelmat on todistettu NP-täydellisiksi, joka tarkoittaa sitä, että yhden NP-täydellisen ongelman ratkaisu polynomisessa ajassa antaa automaattisesti polynomisen ajan ratkaisun kaikkiin NP-ongelmiin.

Esimerkkejä

Kauppamatkustajan ongelman päätösmuoto on yksi tunnetuimmista NP-ongelmista. Siinä kauppamatkustajan täytyy käydä tietyissä kaupungeissa vapaassa järjestyksessä ja lopuksi palata kotiin. Kysymys kuuluu, onko mahdollista löytää reitti, joka on lyhyempi kuin x kilometriä. Minkä tahansa ratkaisuksi tarjotun reitin oikeellisuus voidaan tarkastaa nopeasti eli polynomisessa ajassa. Nopeaa algoritmia ratkaisun löytämiseen ei kuitenkaan tunneta.

Toinen esimerkki NP-ongelmasta on kokonaislukujen tekijöihinjaon päätösongelma. Siinä kysytään, onko annetulla luvulla $n$ alkutekijää, joka on pienempi kuin jokin yläraja $M$.