Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Postojanje NP teshkih problema

[es] :: Art of Programming :: Postojanje NP teshkih problema

[ Pregleda: 4956 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

karas

Član broj: 5574
Poruke: 482
*.127.EUnet.yu



+1 Profil

icon Postojanje NP teshkih problema21.04.2004. u 21:50 - pre 242 meseci
Postoje li NP teshki problemi koji nisu u klasi NP? Primer?


Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.beotel.net

Sajt: localhost


+5 Profil

icon Re: Postojanje NP teshkih problema22.04.2004. u 01:21 - pre 242 meseci
ne razumem pitanje. pitaš za NP probleme koji nisu NP?

ajde pokušaj da preformulišeš to..

 
Odgovor na temu

karas

Član broj: 5574
Poruke: 482
*.66.EUnet.yu



+1 Profil

icon Re: Postojanje NP teshkih problema22.04.2004. u 10:56 - pre 242 meseci
Pitam za NP teshke probleme koji nisu u NP.

Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dial.InfoSky.Net



+2789 Profil

icon Re: Postojanje NP teshkih problema26.04.2004. u 01:31 - pre 242 meseci
Problemi NP težine su problemi iz klase NP. Stvarno pitanje nije korektno formulisano. Pojasni ga.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

karas

Član broj: 5574
Poruke: 482
*.14.eunet.yu



+1 Profil

icon Re: Postojanje NP teshkih problema26.04.2004. u 15:45 - pre 242 meseci
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?

Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dial.InfoSky.Net



+2789 Profil

icon Re: Postojanje NP teshkih problema26.04.2004. u 18:16 - pre 242 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

karas

Član broj: 5574
Poruke: 482
*.83.eunet.yu



+1 Profil

icon Re: Postojanje NP teshkih problema26.04.2004. u 22:45 - pre 242 meseci
Hvala, to me je zanimalo. Inache, knjiga je Algoritmi od M. Zzivkovicca, izdanje Matematichkog fakulteta.

Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."
 
Odgovor na temu

[es] :: Art of Programming :: Postojanje NP teshkih problema

[ Pregleda: 4956 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.