Odrediti klase kompleksnosti zadatih problema

PostPoslato: Ponedeljak, 26. Jun 2017, 13:22
od korisnicko_ime
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]?