NP-teški problemi

NP-teški problemi (nedeterministički u polinomijalnom vremenu teški), predstavljaju klasu problema u računarstvu, koji se neformalno nazivaju teški najmanje kao NP problemi. Problem H je NP-težak ako i samo ako postoji NP-kompletan problem L takav da je polinomijalno svodljiv na H. Drugim rečima, L može biti rešen u polinomijalnom vremenu pomoću proročke mašine sa proročištem za H. Neformalno, možemo da zamislimo algoritam koji može da pozove takvu proroču mašinu kao subrutinu za rešavanje H, i da reši L u polinomijalnom vremenu, ako se poziv subrutine izvršava u jednom koraku. NP-teški problemi mogu biti bilo kog tipa: problemi odlučivanja, problemi pretrage, problemi optimizacije.

Kao posledica ovakve definicije, imamo sledeće iskaze (ovo nisu definicije):

• problem H je najmanje onoliko težak kao L, jer se H može koristiti da se reši L;

• kako je L NP-kompletan problem, i stoga najteži u klasi NP, H je takođe najmanje onoliko težak kao NP, ali on ne mora da bude u klasi NP, i stoga ne mora da bude problem odlučivanja;

• kako se NP-kompletni problemi mogu svoditi jedan na drugi u polinomijalnom vremenu (polinomijalna transformacija), sledi da se svi NP-kompletni problemi mogu u polinomijalnom vremenu svesti na H, i stoga se svi problemi iz klase NP mogu svesti na H;

• ako postoji polinomijalni algoritam za bilo koji NP-težak problem, onda postoji polinomijalni algoritam za sve probleme u klasi NP, i stoga je P = NP;

• ako P ≠ NP, tada NP-teški problemi nemaju rešenje u polinomijalnom vremenu, ali P = NP ne znači automatski da NP-teški problemi mogu biti rešeni u polinomijalnom vremenu;

• ako optimizacioni problem H ima NP-kompletnu verziju problema odlučivanja L, tada je H NP-težak;

• ako je H iz NP klase, tada je H takođe NP-kompletan problem;

Česta greška je da se misli da NP iz NP-teški problemi znači nepolinomijalni. Mada postoje široko rasprostranjene sumnje da ne postoje polinomijalni algoritmi za ove probleme, ovo nije dokazano.

Primeri

Primer NP-teškog problem je problem zbira podskupa (problem odlučivanja), koji glasi: ako je dat skup celih brojeva, da li postoji neprazan podskup ovog skupa, takav da zbir njegovih članova daje nulu? Ovo je da/ne pitanje, i takođe je NP-komletno. Još jedan primer NP-teškog problema je optimizacioni problem pronalaženja najjeftinijeg puta kroz sve čvorove težinskog grafa. Ovaj problem je poznat pod imenom problem trgovačkog putnika.

Postoje i problemi odlučivanja koji su NP-teški, ali nisu NP-kompletni, na primer halting problem. Ovaj problem glasi: ako je dat program, i njegov ulaz, da li će se program zaustaviti, ili će se beskonačno izvršavati? Ovo je da/ne pitanje, i stoga je problem odlučivanja. Lako je dokazati da je halting problem NP-težak, ali da nije NP-kompletan. Na primer, Bulovski SAT problem se može svesti na halting problem transformisanjem na opis Tjuringove mašine koja isprobava sve istinitosne vrednosti i kada nađe jednu kombinaciju koja zadovoljava formulu staje, dok u suprotnom ulazi u beskonačnu petlju. Takođe je lako videti da halting problem nije NP, jer su svi problemi iz klase NP odlučivi u konačnom broju operacija, dok halting problem u opštem slučaju nije.

Literatura

Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5.