U području računalnih znanosti postoji jedno od najpoznatijih neriješenih problema – je li skup problema koji se mogu riješiti u razumnom vremenu jednak onome čije rješenje možemo brzo provjeriti. Iako se na prvi pogled čini apstraktnim, ovaj problem utječe na tehnologije koje svakodnevno koristimo, od sigurnosti internetske komunikacije do optimizacije logističkih sustava. U nastavku ćemo ovu temu razložiti na jednostavan način, uz dovoljno detalja da i stručnjaci pronađu korisne informacije.
Sadržaj...
Što znače oznake P i NP?
Oznaka P označava skup problema koji se mogu riješiti u polinomijalnom vremenu, što znači da vrijeme rješavanja raste najviše polinomijalno s veličinom ulaza. Primjeri uključuju sortiranje popisa, pronalaženje najkraćeg puta u mreži ili provjeru je li broj prost.
Oznaka NP označava skup problema za koje, iako možda ne znamo kako ih brzo riješiti, možemo provjeriti ispravnost rješenja vrlo brzo. Drugim riječima, ako netko izda rješenje, mi ga možemo u kratkom roku potvrditi.
Zašto je razlika važna?
Razlika između P i NP ima praktične posljedice. Ako se pokaže da su P i NP jednaki, to bi značilo da svako teško provjerivo pitanje možemo riješiti jednako brzo. To bi, primjerice, učinilo trenutno nepremostive šifre lako probijajućima, što bi ugrozilo sigurnost internetske komunikacije.
S druge strane, ako je P različito od NP, tada postoje zadaci koji su inherentno teški – ne postoji algoritam koji bi ih riješio u razumnom vremenu, bez obzira na napredak tehnologije. To bi objasnilo zašto su neke optimizacijske probleme toliko zahtjevne i zašto se u praksi oslanjamo na heuristike.
Primjeri iz svakodnevnog života
Razmotrimo dva jednostavna zadatka:
\
