NP-sunkumas (NP-hard) ir NP-užbaigtumas: apibrėžimas ir pavyzdžiai

NP-sunkumas ir NP-užbaigtumas paaiškinti aiškiai: definicijos, skirtumai ir praktiniai pavyzdžiai (keliaujančio pardavėjo, Halting) — suprantamai ir naudinga.

NP-sunkumas (NP-hard) reiškia, kad tam tikras sprendžiamasis (dažniausiai "taip/ne") uždavinys yra bent jau toks pat sunkus kaip bet kuris kitas uždavinys, kurio sprendinį galima greitai (polinominiu laiku) patikrinti. Formaliau: problema L yra NP-sunki, jei kiekviena problema iš klasės NP reducinuojasi į L polinominio laiko dauginimo (many-one) redukcija. Tai reiškia, kad turint algoritmą, kuris sprendžia L efektyviai, galėtumėme juo pasinaudoti spręsdami bet kurią kitą NP klasės problemą efektyviai.

Kas yra NP ir NP-užbaigtumas (NP-complete)?

NP (Nondeterministic Polynomial time) yra klasė sprendžiamųjų uždavinių, kurių teisingą atsakymą galima patikrinti polinominio laiko algoritmo pagalba, jei pateikiamas sprendimas (pvz., įrodymas arba "atlyginis" įrašas). Problema yra NP-užbaigta (NP-complete), jei ji yra tiek NP, tiek NP-sunki. Kitaip tariant, tai yra sunkiausios problemos NP klasėje: jei bent viena NP-užbaigta problema turi polinominio laiko sprendimą, tuomet visos NP problemos turi tokį sprendimą (ir tada P = NP).

Redukcijos—kodėl tai svarbu

Redukcija (dažniausiai naudojama polinominio laiko many-one redukcija, dar vadinama Karp redukcija) yra formalus būdas parodyti, kad viena problema yra ne lengvesnė už kitą: duodami instanciją A problemos A, per polinominio laiko procedūrą ją paverčiame instancija B problemos B taip, kad A turi teigiamą atsakymą tada ir tik tada, kai B turi teigiamą atsakymą. Jei kiekvieną NP problemą galima tokiu būdu paversti į problemą X, tai X yra NP-sunki.

Pavyzdžiai

• Keliaujančio pardavėjo sprendinio (TSP) uždavinys, kaip viktorinos forma (sprendinys: "ar egzistuoja aplankymo maršrutas, kurio ilgis ≤ L?") — tai klasikinis pavyzdys NP-užbaigtos problemos, kai pateikiame sprendinį (konkretų maršrutą), jį lengva patikrinti polinominiu laiku (apskaičiuoti maršruto ilgį). Originaliame tekste pateikta versija: „Keliaujantis pardavėjas nori aplankyti 100 miestų… jis turi ribotas benzino atsargas… ar galės aplankyti visus miestus, nepritrūkęs benzino?“ Ši "taip/ne" versija yra NP, ir, su tinkamomis parametrizacijomis, NP-užbaigta — ji atitinka keliaujančio pardavėjo uždavinį.
• Optimizacijos vs. sprendžiamieji uždaviniai: verta pabrėžti skirtį: TSP optimizacijos uždavinys (rasti trumpiausią maršrutą) yra NP-sunkus, bet ne būtinai priskiriamas NP klasės, nes tai nėra "taip/ne" forma. Dažnai optimizacijos uždaviniai yra NP-sunki arba NP-sunki ir nepriklauso NP, tačiau jų susijusios sprendžiamųjų variantų formos gali būti NP-užbaigtos.
• SAT (boolean satisfiability) ir 3-SAT: pirmoji problema, įrodyta kaip NP-užbaigta (Cook–Levin teorema) yra SAT: ar egzistuoja reikšmių priskyrimas, tenkinantis išraišką? 3-SAT (riboto tipo SAT) taip pat yra NP-užbaigta. Daugelis kitų NP-užbaigtų problemų yra įrodytos per redukcijas iš SAT arba kitų žinomų NP-užbaigtų problemų.
• Undecidable problemų pavyzdys, dažnai minima šalia NP-sunkumo: originaliame tekste pateiktas klausimas:

  while(true){ tęsti; }

  ir klausimas: jei kas nors pradeda programą, kuri tiesiog vyksta ir niekada nesustoja, ar ji veiks amžinai? Tai yra susiję su stabdymo problema (halting problem), kuri yra ne tik ne NP, bet ir nepakeičiama (undecidable) — nėra algoritmo, galinčio visiems įėjimams atsakyti teisingai. Tačiau svarbu pažymėti, kad nors daugelis nepakeičiamų problemų yra "dar sunkesnės" nei NP, jas galima formaliai lyginti su NP per redukcijas: pavyzdžiui, daug NP problemų galima redukuoti į stabdymo problemą, tad stabdymo problema gali būti laikoma bent jau "mažmenine" prasme labai sunkiu pavyzdžiu (kartais sakoma, kad ji yra NP-sunki tam tikroje prasme), tačiau pagrindinis skirtumas yra tas, jog NP-sunkumo sąvoka tradiciškai taikoma sprendžiamoms problemoms ir naudoja polinominio laiko redukcijas. Stabdymo problema yra ne tik ne NP, bet ir nealgoritmiškai sprendžiama.

Ką reiškia praktikoje

• NP-užbaigtų problemų (ir daugumos NP-sunkių uždavinių) atveju nėra žinomo polinominio laiko algoritmo. Tai skatina kurti heuristikas, apytikslius algoritmus (approximation algorithms), parametrines metodikas ir eksponentinius bet tvarkingus (exact exponential) algoritmus, priklausomai nuo reikalavimų.
• Jei kas nors rastų polinominio laiko sprendimą vienai NP-užbaigtai problemai (pvz., SAT ar TSP sprendimo variantui), tai reikštų, kad P = NP — vienas iš svarbiausių atvirų klausimų kompiuterių moksle. Dėl to NP-užbaigtos problemos yra laikomos „sunkiausiomis“ NP klasėje.
• Geras praktinis požiūris: atpažinti, ar jūsų uždavinys priklauso NP ar yra NP-sunkus, tada pasirinkti tinkamą strategiją: specializuotas algoritmas konkretiems duomenims, aproksimacija, heuristika arba problemos pertvarkymas į sprendžiamą atvejį.

Santrauka

NP-sunki problemos: į jas galima nukreipti (redukuoti) visas NP problemas — jos yra bent jau tokios pat sunkios, bet gali būti ir sunkesnės (pvz., nealgoritmiškos). NP-užbaigtos problemos: jos yra NP ir tuo pačiu NP-sunkios — tai sunkiausios problemos NP klasėje. Pagrindinė praktinė išvada: NP-užbaigtumui nustatyti naudojamos redukcijos; daug NP-užbaigtų problemų sprendžiamos heuristiškai arba apytiksliai, nes efektyvaus universalaus sprendimo nėra žinoma.

Originaliose eilutėse panaudoti terminai: NP-užbaigtumu, algoritmu, keliaujančio pardavėjo uždaviniu pateikiami kaip nuorodos į susijusią informaciją.

Klausimai ir atsakymai

K: Kas yra NP sunkiai sprendžiama problema?

Klausimas: Ar galima greitai patikrinti, ar visų NP sunkiai sprendžiamų uždavinių sprendimas yra teisingas?

Klausimas: Kaip vadinama kategorija, apimanti NP sunkumo uždavinius, kurie taip pat yra NP uždaviniai?

K: Ar visi NP sunkūs uždaviniai yra NP-užbaigti?

K: Ar NP sunkiai sprendžiamus uždavinius lengva išspręsti?

K: Ar yra kokių nors privalumų sprendžiant NP sudėtingus uždavinius?

K.: Ar vykdomi moksliniai tyrimai, susiję su NP sudėtingų uždavinių sprendimu?

Paieška pagal raidę