NP-težkost: NP-težki in NP-popolni problemi — TSP in problem ustavljivosti

Osnovne definicije

NP-težak problem je odločilni (da/ne) problem, za katerega velja: iskanje rešitve je vsaj tako težko kot iskanje rešitve za katerikoli drug problem, katerega rešitev je mogoče hitro (polinomno) preveriti. Bolj formalno: problem B je NP-težak, če za vsak problem A iz razreda NP obstaja polinomska redukcija A ≤p B (vsako instanco A lahko v polinomskem času preoblikujemo v instanco B tako, da odgovora "da" in "ne" sovpadata).

Pomembna ločnica je med NP-težkimi problemi in NP-problemi (razred NP). NP je množica odločilnih problemov, kjer za vse primerke, za katere je odgovor "da", obstaja kratko dokazilo (potrdilo, certificate), ki ga je mogoče v polinomskem času preveriti z determinističnim algoritmom. Nekateri NP-težki problemi so hkrati v NP; ti se imenujejo NP-popolni. Drugi NP-težki problemi morda niso v NP — so lahko še težji ali celo nerešljivni.

Kaj pomeni NP-popoln

Problem je NP-popoln, če izpolnjuje dve lastnosti:

• je v NP (obstaja polinomski verifikator za pozitiven odgovor),
• je NP-težak (vsak problem iz NP se lahko polinomsko reducira nanj).

Če bi našli polinomski algoritem za katerikoli NP-popoln problem, bi s pomočjo redukcij lahko v polinomskem času reševali vse probleme v NP (to je jedro odprtega vprašanja P vs NP).

Primer: problem potujočega prodajalca (TSP)

Primer problema, ki ga je vsaj tako težko rešiti kot katerikoli drug problem, za katerega lahko hitro preverimo rešitve in ki je tudi hitro preverljiv (je hkrati NP-trd in NP):

Potujoči prodajalec želi z vožnjo obiskati 100 mest, potovanje pa začeti in končati doma. Ker ima omejene zaloge bencina, lahko prevozi le 10.000 kilometrov. Zanima ga, ali lahko obišče vsa mesta, ne da bi mu zmanjkalo bencina.

Tako postavljen problem je odločilna verzija TSP: "Obstaja Hamiltonov krog z dolžino ≤ L?" To obliko lahko hitro preverimo — če nam kdo poda krog (zaporedje mest), lahko v polinomskem času seštejemo razdalje in preverimo, ali je ≤ 10.000. Hkrati velja, da je odločilna verzija problema potujočega prodajalca NP-popolna v splošnem (če so razdalje poljubne). Optimizacijska verzija (najkrajša pot) je NP-težka.

Če bi vprašanje reševali z nasilnim preizkušanjem vseh možnih permutacij, bi to za 100 mest bilo eksponentno drago, zato za velike instance ni znan polinomski algoritem. Kljub temu, če kdo predloži kandidatno pot, jo lahko z algoritmom hitro preverimo, ali ustreza omejitvi. Ta problem je znan tudi kot problem potujočega prodajalca.

Opomba: za nekatere posebne različice (npr. metrika TSP, kjer trianglna neenakost velja) obstajajo dobro delujoče približne ali heuristične metode, vendar še vedno ni znan polinomni algoritem, ki bi rešil splošni primer natančno.

Primer: problem ustavljivosti (halting problem)

Primer problema, ki je vsaj tako težak kot kateri koli problem iz NP, vendar ga ni mogoče hitro preveriti (je NP-težak, vendar ni v NP):

Razmislimo o vprašanju: če nekdo zažene program, ki se v nedogled izvaja, na primer

while(true){ nadaljevanje; }

ali bo tak program deloval večno (se nikoli ne ustavil)? To je poenostavljen opis problema ustavljivosti. Treba je poudariti, da je problem ustavljivosti (v splošni obliki) nerešljiv — Turing je pokazal, da ne obstaja algoritem, ki bi za vsak program in vhod odločil, ali se bo program ustavil.

Ker je nerešljiv, ne more biti v razredu NP (NP zajema le probleme, ki so odločljivi in imajo polinomsko preverljivo potrdilo za pozitiven odgovor). Vendar je problem ustavljivosti v smislu računskih redukcij "vsaj tako težak" kot mnogi problemi iz NP: zgrajeni lahko program, ki išče rešitev poljubnega NP-problema in se ustavi natanko takrat, ko obstaja dokaz. Zato mnoge nerešljive probleme obravnavamo kot NP-težke v širšem smislu — so vsaj tako zahtevni kot problemi iz NP, pogosto pa še težji (nerešljivi).

Redukcije in pomen v praksi

Ključni koncept pri dokazovanju NP-težkosti ali NP-popolnosti so polinomske redukcije. Če lahko problem A v polinomskem času pretvorimo v problem B tako, da rešitev B daje rešitev A, potem je B vsaj tako težek kot A. S tem pristopom se dokaže NP-težkost: iz znanega NP-popolnega problema (npr. SAT) se zgradi redukcija na ciljnega problema.

V praksi to pomeni:

• če je problem NP-popoln, iskati polinomsko natančno rešitev za velike instance običajno ni smiselno — raje se uporabljajo približne metode, heuristike ali eksaktni algoritmi s pristranskostjo za manjše instance;
• če je problem NP-težak, a ni v NP (npr. nerešljiv ali celo težji), potem splošne rešitve ni — reševanje zahteva posebne omejitve ali drugačne pristope;
• če bi se kdaj dokazalo P = NP, bi to pomenilo, da obstajajo polinomski algoritmi za vse NP-popolne probleme, kar bi velikokrat spremenilo računalništvo in kriptografijo; trenutno pa je to odprto vprašanje.

Zaključek

Strnemo lahko takole: NP-težak pomeni "vsaj tako težek kot kateri koli problem v NP"; NP-popoln pomeni "v NP in hkrati NP-težak". Problem potujočega prodajalca (odločilna verzija) je klasičen primer NP-popolnega problema (rešitve je mogoče preveriti hitro in je težko najti), medtem ko so nekateri problemi, kot problem ustavljivosti, še bolj zahtevni — nerešljivi in zato ne sodijo v NP, a so v širšem smislu NP-težki oziroma še huje težavni.

Vprašanja in odgovori

V: Kaj je NP-težak problem?

V: Ali je mogoče hitro preveriti rešitev za vse NP-težke probleme?

V: Kako se imenuje kategorija za NP-težke probleme, ki so tudi NP-problemi?

V: Ali so vsi NP-težki problemi NP-popolni?

V: Ali je NP-težke probleme lahko rešiti?

V: Ali ima reševanje težkih NP-problemov kakšne prednosti?

V: Ali potekajo raziskave na področju reševanja NP-težkih problemov?

Išči po črki