Problemy NP, P, NP = P

0

Słyszałem że są przewidziane duże nagrody za rozwiązanie niektórych problemów.

Gdzie mam się zgłosić po kasę, gdy rozwalę w czasie wielomianowym...
przykładowo, taki problemik komiwojażera, lub inny taki NP. :)

No i jeszcze tak w ogóle, gdy pokażę rozwiązanie to mnie tam nie wyrolują,
powiedzą że to niedobre, a za kwartał jakiś
prof. doc. inż. kard. o. płk Kombinatorowiczgadacz,
zgłosi moje rozwiązanie i będzie nowy Mr cwaniak w książkach,
tak jak ci wszyscy: Euler, Gauss, Arystoteles i Gagarin... którzy wyrypali swoich uczniów i znajomych. :[

0

He, he. Dobre. Te problemy to problemy natury bardziej matematycznej niz informatycznej. Nie obejdzie sie pewnie bez kilku publikacji w prasie fachowej i dowodu na kilkaset stron. Do dziela :D :D :D

0
franc napisał(a)

Gauss(...) którzy wyrypali swoich uczniów i znajomych. :[

Kogo Gauss wyrypał? :>

Jeżeli uda Ci się już napisać odpowiedni algorytm, to spokojnie możesz zgłosić do ACM. Nie sądzę, by Cię tam wyrolowali :)

0
Dryobates napisał(a)

Kogo Gauss wyrypał?

Ten to wyjątkowa bestyja!
Wykończy wielu, z tego powodu wymienię jedynie najbliższych:

  • Joanna - pierwsza żona,
  • Louis - syn - długo nie pożył, szybko wykończon pod ojcowskim biczem!
  • Fryderyka - druga żona - ta szczególnie długo męczona przez tego ... :[
  • Wilhelmina - córka, zmuszana do żmudnego dopracowywania teorii ojca,
    długo tego nie wytrzymała (biedna kruszyna)
  • Wilhelm - syn, nie mógł wytrzymać tego despotyzmu i uciekł do Ameryki,
    gdzie musiał robić w polu jak niewolnik!
  • Teresa - córka, zmuszona była opiekować się tym... [diabel] i w efekcie tego zmarnowała swe młodzieńcze życie.
0

No bez przesady... Sugerujesz ze Gauss zmusil ich do opracowania teorii, ktore potem oglosil jako swoje? Nie doginaj...

0
spc napisał(a)

No bez przesady... Sugerujesz ze Gauss zmusil ich do opracowania teorii, ktore potem oglosil jako swoje? Nie doginaj...

To jedynie taka egzotyczna interpretacja.
No, ale mimo wszystko facet miał urozmaicone życie...

"Ask her to wait a moment - I am almost done. "
Carl Friedrich Gauss (1777-1855),
while working, when informed that his wife is dying.
:d

0

No ja zdaje sobbie sprawe ze to raczej nie do konca serio jest, tylko moje pytanie brzmi: O co kaman w tym topicu?

0

Jak to o co chodzi?
O szmal chodzi!

Pracy mało, bezrobocie wielkie, to nagrody trzeba zgarniać chociaż, bo... żreć się chce! [!!!]

0

publikacja w prasie-jakimś pożądnym piśmie naukowym i nikt Ci już tego nie zabierze

0

Jednak problem: NP = P albo NP != P jest raczej nierozstrzygalny, a to właśnie za to płacą 1M$.

Samo opracowanie jakiegoś algorytmu, który rozwali jeden problem NP-zupełny w czasie wielomianowym nic tu nie pomoże.
Będzie to jedynie dowód tego, że ten jeden problem jest klasy P, a nie że P = NP! :D

Ale z drugiej strony - dowolny problem klasy NP-zupełny można (podobno) przerobić w czasie wielomianowym na każdy inny problem klasy NP-z.
Zatem mając rozwiązanie jednego w czasie P, mamy wszystkie też w P...
i wtedy musi być: P = NP.

Ktoś potrafi podać przykład takiego przerobienia jednego problemu NP-zup. na inny? :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1