Imam sledeća tri primera:
1. Dat je niz od [inlmath]n[/inlmath] tačaka u dvodimenzionom koordinatnom sistemu i indeksi dviju tačaka iz tog niza. Da li je najkraća zatvorena putanja koja prolazi kroz sve tačke kraća od najkraće putanje između datih dviju tačaka?
2. U socijalnoj mreži od [inlmath]n[/inlmath] osoba, da li najveći skup osoba koje se međusobno poznaju sadrži više od [inlmath]k[/inlmath] osoba?
3. Da li je u električnoj mreži koja povezuje međusobno svaki od [inlmath]n[/inlmath] gradova najkraća dužina dalekovoda koji samo jednom prolazi kroz svaki grad i povezuje sve gradove u zatvorenu mrežu manja od [inlmath]k[/inlmath]?
Odrediti kojim klasama kompleksnosti pripadaju ovi problemi pod pretpostavkom da je [inlmath]P\neq NP[/inlmath].
Kako odrediti kojim klasama kompleksnosti pripadaju ovi problemi? Da li postoji generalizovani postupak?
Šta znači da je [inlmath]P\neq NP[/inlmath]?