[ karas @ 21.04.2004. 21:50 ] @
Postoje li NP teshki problemi koji nisu u klasi NP? Primer?

[ -zombie- @ 22.04.2004. 01:21 ] @
ne razumem pitanje. pitaš za NP probleme koji nisu NP?

ajde pokušaj da preformulišeš to..
[ karas @ 22.04.2004. 10:56 ] @
Pitam za NP teshke probleme koji nisu u NP.
[ Nedeljko @ 26.04.2004. 01:31 ] @
Problemi NP težine su problemi iz klase NP. Stvarno pitanje nije korektno formulisano. Pojasni ga.
[ karas @ 26.04.2004. 15:45 ] @
Prvo da navedem dve definicije iz knjige, jer postoji razlika izmedju NP i NP-teshkih problema.

Problem X je NP-tezzak problem ako je svaki problem iz klase NP polinomijalno svodljiv na X.

Problem X je NP-kompletan problem ako (1) pripada klasi NP, i (2) X je NP-tezzak.

Otuda mi se namecce pitanje postoje li problemi koji jesu NP-teshki ali nisu u NP. Drugim rechima: da li je klasa NP-teshkih problema vecca od klase NP?
[ Nedeljko @ 26.04.2004. 18:16 ] @
Ne znam koju knjigu koristiš, ali njen autor očigledno koristi nestandardnu terminologiju. Standardne definicije bi bile:

1. NP problem je problem koji se može rešiti u polinomijalnom vremenu na NEDETERMINISTIČKIM mašinama.

2. NP je klasa svih NP problema.

3. NP kompletan problem je NP problem na koji je na DETERMINISTIČKIM mašinama polinomijalno svodljiv svaki drugi NP problem.

Koliko vidim ti pod NP teškim problemima podrazumevaš NP kompletne probleme, kao i one probleme koji nisu NP. Drugim rečima, kod tebe je NP težak problem isto što i problem čija je težina NAJMANJE NP. E, pa onda se tvoje pitanje svodi na to da li postoje problemi koji nisu u klasi NP, to jest oni čija te težina VEĆA od NP. Ima ih. Postoji jedna zanimljiva teoreme (zovu je speed up teorema) koja glasi:

Neka je bilo koja algoritamski izračunljiva funkcija. Tada postoji podskup A skupa prirodnih brojeva takav da je problem pripadnosti tom skupu algoritamski rešiv, ali tako da za svaki program P koji rešava taj problem postoji program Q koji takođe rešava taj problem, ali tako da postoji broj m takav da za svako k>m program Q ispituje da li broj k pripada skupu A najmanje f(k) puta brže nego program P.

Ako je na primer , onda će takav problem biti užasno težak i negova težina će itekako nadmašiti NP. Inače, ovu teoremu možeš naći u knjizi Computability čiji je autor Nigel Cutland.
[ karas @ 26.04.2004. 22:45 ] @
Hvala, to me je zanimalo. Inache, knjiga je Algoritmi od M. Zzivkovicca, izdanje Matematichkog fakulteta.