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ę.
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- 13
Komentarze (13)
najlepsze
Milijon proszę przesłać w nieużywanych banknotach.
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
http://www.wykop.pl/link/433691/p-nie-jest-rowne-np/
http://www.wykop.pl/link/433769/dowod-na-to-ze-p-np/
Komentarz usunięty przez moderatora
Komentarz usunięty przez moderatora
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 wtw
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2) ma minimum (w 0)
żeby przetłumaczyć alternatywę