Problem P = NP rozwiązany?

Niewykluczone, że rozwiązano jedną z najważniejszych zagadek informatyki i jednocześnie jeden z siedmiu tzw. problemów milenijnych. Jeżeli potwierdzą się wyliczenia Vinaya Deolalikara, nie tylko przejdzie on do historii, ale i zyska milionową nagrodę.

[Marro]

i pomyśleć, że problem P = NP dla mnie jeszcze parę minut temu w ogóle nie istniał.

[extralion]

jeszcze jakby tak problem JP rozwiązali

[AtoMan]

@extralion: JP != JP2.

Milijon proszę przesłać w nieużywanych banknotach.

[fik43pobme]

Bedzie to oznaczalo, ze to juz 2 z 7 zadan milenijnych, ktore zostaly rozwiazane,. Pierwszym z rozwiazanych zadan milenijnych bylo zadanie dotyczace hipotezy Poincare'a, i zostalo rozwiazane przed 7 laty przez rosjanina Grigorjia Jakowlewicza Perelmana. Co ciekawe, do tej pory facet nie odebral nagrody :)

[k.....g]

@fik43pobme: i nie ma zamiaru jej odebrać, bo stwierdził, że dobrze mu się żyje. Tak w ogóle to mieszka w jakiejś szopie.

[trawiasty]

Czas potrzebny do wykonania zadania to P, a czas potrzebny do weryfikacji wyniku to NP. Jeśli zatem P=NP, oznacza to, że każdy problem, którego rozwiązanie może być szybko zweryfikowane, może zostać też szybko rozwiązany.

Pierwsze zdanie jest strasznie nieścisłe. Fixed:

Dla problemów NP weryfikacja rozwiązania ma mieć złożoność wielomianową (czyli można to zrobić względnie szybko), zaś dla problemów P znalezienie rozwiązania ma mieć taką zlożoność. Jeśli zatem P=NP, oznacza to, że każdy

[PanKogito]

No to będzie odkrycie. Koleś urodził się w 1971 i jeśli wszystko się potwierdzi to i na fieldsa się załapie.

[Archeopteryx_litographica]

Było

http://www.wykop.pl/link/433691/p-nie-jest-rowne-np/

http://www.wykop.pl/link/433769/dowod-na-to-ze-p-np/

[Ardai]

http://www.technologyreview.com/computing/26086

[darokrol]

aha

[gdzie_jest_krzyz]

@darokrol: Jakoś sobie nie wyobrażam takiego dowodu ... musi uwzględniać wszelkie możliwe klasy algorytmów ... jak zamianę na ciągły problem ...

Na przykład w 3SAT pytaniem jest czy można tak zawartościować zmienne, żeby wszystkie zadane alternatywy trójek z negacjami (np. x lub (nie y) lub z) były spełnione.

No to potraktujmy zmienne jako liczby rzeczywiste - alternatywa (x lub y) jest spełniona