U računalnoj znanosti pojmovi poput NP i NP‑potpuna često se spominju, ali za mnoge čitatelje ostaju nejasni. Ovaj članak razjašnjava što zapravo znači NP‑problem, kako se razlikuje od drugih klasifikacija problema i zašto je od iznimne važnosti za razvoj algoritama, kriptografiju i mnoga druga područja.
Sadržaj...
Osnovni pojmovi: P, NP i NP‑potpuna
Prvo je važno razumjeti tri ključne skupine problema:
- P – skup problema koji se mogu riješiti u polinomijalnom vremenu, tj. postoji algoritam čije vrijeme rješavanja raste kao polinom od veličine ulaza.
- NP – skup problema čija je rješenja lako provjeriti u polinomijalnom vremenu. To znači da, ako netko izda rješenje, mi možemo brzo provjeriti je li to rješenje ispravno.
- NP‑potpuna – podskup NP‑problema koji su najteži u tom skupini. Ako se nađe polinomijalni algoritam za jedan NP‑potuni problem, tada bi se mogao riješiti i svaki drugi NP‑problem u polinomijalnom vremenu.
Najčešće se postavlja pitanje: je li P jednako NP? Do danas nema dokaza da su jednaki, a većina stručnjaka smatra da nisu. To je jedan od najvažnijih otvorenih problema u teoriji računalstva.
Primjeri NP‑problema u svakodnevnom životu
Da bi se bolje razumjelo što znači NP‑problem, pogledajmo nekoliko poznatih primjera:
- Problem putovanja prodavača (TSP) – Prodavač mora posjetiti skup gradova i vratiti se na početnu lokaciju uz minimalnu ukupnu udaljenost. Rješenje se može lako provjeriti, ali pronalaženje optimalnog rješenja je izuzetno teško.
- Problem zadovoljavanja (SAT) – Postoji li kombinacija varijabli koja zadovoljava određenu logičku formulu? SAT je prvi problem koji je dokazano NP‑potpun.
- Problem bojenja grafa – Koliko boja je potrebno da se obojaju čvorovi grafa tako da nijedna susjedna čvorova ne dijeli istu boju? Provjera rješenja je jednostavna, ali pronalaženje minimalnog broja boja predstavlja izazov.
- Problem raspoređivanja (Scheduling) – Kako rasporediti radne zadatke na strojeve tako da se minimizira ukupno vrijeme završetka? Rješenje se lako provjerava, ali pronalaženje optimalnog rasporeda je iznimno teško.
- Problem kombinatornog optimiranja (Knapsack) – Kako odabrati podskup predmeta s maksimalnom vrijednošću, a da ukupna težina ne prelazi kapacitet? Provjera rješenja je brza, ali pronalaženje optimalnog je teško.
Zašto su NP‑problemi ključni za tehnologiju
NP‑problemi su temelj mnogih tehnologija koje svakodnevno koristimo. Na primjer, kriptografske metode poput RSA‑a oslanjaju se na činjenicu da je pron
