NP kietumas
NP sunkus uždavinys yra "taip/ne" uždavinys, kurio sprendinį rasti yra bent jau taip pat sunku, kaip rasti sunkiausio uždavinio, kurio sprendinį galima greitai patikrinti kaip teisingą, sprendinį. Kai kurie NP sunkūs uždaviniai yra tokie, kurių veikiantį sprendinį galima greitai patikrinti (NP uždaviniai), o kai kurie - ne. NP sunkūs uždaviniai, kurie taip pat yra NP uždaviniai, priskiriami kategorijai, vadinamai NP-užbaigtumu.
Problemos, kurią išspręsti yra bent jau taip pat sunku, kaip ir bet kurią kitą problemą, kurios sprendinius galime greitai patikrinti ir kuri taip pat yra greitai patikrinama (ji yra ir NP-sunki, ir NP), pavyzdys:
Keliaujantis pardavėjas nori aplankyti 100 miestų važiuodamas automobiliu, kelionę pradėdamas ir baigdamas namuose. Jis turi ribotas benzino atsargas, todėl iš viso gali nuvažiuoti tik 10 000 km. Jis nori sužinoti, ar galės aplankyti visus miestus, nepritrūkęs benzino.
Žmonės nežino, kaip šią problemą išspręsti greičiau nei išbandant visus galimus atsakymus, tačiau jei randamas sprendimas, leidžiantis pardavėjui tai padaryti, galime algoritmu patikrinti, ar jis teisingas. Šis uždavinys dar vadinamas keliaujančio pardavėjo uždaviniu.
Problemos, kurią išspręsti yra bent jau taip pat sunku, kaip ir bet kurią kitą problemą, kurios sprendinius galime greitai patikrinti, bet kurios negalima greitai patikrinti, pavyzdys (ji yra NP-sunki, bet nėra NP):
jei kas nors pradeda programą, kuri tiesiog vyksta,
while(true){ tęsti; }ir niekada nesustoja, ar jis veiks amžinai?
Nėra žinomo būdo, kaip rasti visų tokio pobūdžio problemų sprendimą, ir to taip pat negalima patikrinti.
Klausimai ir atsakymai
K: Kas yra NP sunkiai sprendžiama problema?
A: NP sunkus uždavinys - tai informatikoje naudojamas matematinių uždavinių tipas, t. y. "taip" ir "ne" uždavinys, kurio sprendinį rasti yra bent jau taip pat sunku, kaip rasti sunkiausio uždavinio, kurio sprendinį galima greitai patikrinti kaip teisingą, sprendinį.
Klausimas: Ar galima greitai patikrinti, ar visų NP sunkiai sprendžiamų uždavinių sprendimas yra teisingas?
Atsakymas: Ne, tik kai kurių NP sunkių uždavinių, vadinamų NP uždaviniais, sprendinius galima greitai patikrinti.
Klausimas: Kaip vadinama kategorija, apimanti NP sunkumo uždavinius, kurie taip pat yra NP uždaviniai?
A: NP sunkūs uždaviniai, kurie taip pat yra NP uždaviniai, priklauso kategorijai, vadinamai NP-užbaigtumas.
K: Ar visi NP sunkūs uždaviniai yra NP-užbaigti?
A: Ne, ne visi NP sunkūs uždaviniai yra NP-užbaigti. Šiai kategorijai priklauso tik tie, kurie yra ir NP uždaviniai.
K: Ar NP sunkiai sprendžiamus uždavinius lengva išspręsti?
A: Ne, NP sunkiai sprendžiamus uždavinius nėra lengva išspręsti. Tiesą sakant, rasti jų sprendinį yra bent jau taip pat sunku, kaip rasti sunkiausio uždavinio, kurio sprendinį galima greitai patikrinti, ar jis teisingas, sprendinį.
K: Ar yra kokių nors privalumų sprendžiant NP sudėtingus uždavinius?
Atsakymas: Taip, NP sunkiai sprendžiamų uždavinių sprendimas gali būti naudingas įvairiose srityse, pavyzdžiui, informatikos, fizikos ir socialinių mokslų, nes jiems spręsti gali prireikti sudėtingų skaičiavimų ir modeliavimo.
K.: Ar vykdomi moksliniai tyrimai, susiję su NP sudėtingų uždavinių sprendimu?
A.: Taip, tyrimai sprendžiant NP sunkiai sprendžiamus uždavinius vyksta, nes šie uždaviniai ir toliau aktualūs įvairiose srityse, o efektyvių algoritmų ir sprendimų radimas gali turėti didelę reikšmę.
