Da li se sećate šta je NP-kompletan problem? Čime se razlikuje od običnog NP?

NP (nondeterminističko polinomijalno vreme) — to je klasa problema za koje se rešenje može proveriti u polinomijalnom vremenu. To jest, ako imate kandidata za odgovor, možete brzo proveriti da li je tačan ili ne.

NP-kompletni problemi su podskup NP koji su u isto vreme i naj"teži" u ovoj klasi. Ako bi neko pronašao polinomijalni algoritam za rešavanje bilo kog NP-komplet problema, svi problemi iz NP bi se mogli rešiti u polinomijalnom vremenu.

Glavna razlika:

• NP — problemi čije se rešenje može brzo proveriti.
• NP-kompletni — problemi u NP na koje se može svesti bilo koji drugi NP problem (tj. oni su "najkomplikovaniji" u NP).

Primer: problem maksimalnog klika u grafu je NP-kompletan, a problem provere da li je podskup elemenata suma jednaka zadatom broju je u NP.