NP (vaativuusluokka)
From Wikipedia, the free encyclopedia
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.[1]