P≠NP

[pomruk]

Niejaki Norbert Blum opublikował a arXiv pracę, w której - jak twierdzi - udowodnił, że P≠NP.
Chodzi o znany problem matematyczny:
P versus NP problem

Tekst pracy:
arxiv.org/pdf/1708.03486.pdf

[nikodem321]

pomruk, bez komentarza autora taki wpis jest mało ciekawy.

"p nie równa się np" PLUS odsyłka do Wikipedii po angielsku.

[pomruk]

Tak, zdaję sobie teraz z tego sprawę. Sam protestowałem gdy umieszczano takie lakoniczne notki. Cóż, moja wina, przyznaję.
Nie jestem matematykiem ani informatykiem, bałem się popełnić jakieś głupstwo. Jednocześnie uważałem, że temat jest na tyle istotny, że zasługuje na wzmiankę. Potraktowałem go więc tak, jak się traktuje w TV doniesienia "na pasku". Jako "breaking news" - coś w rodzaju wpisu "z ostatniej chwili - bozon Higgsa wreszcie znaleziony!", nie zaś jako wpis typu "ziemniaki tuczą" plus link do portalu "Kuchnia Polska".
Ponieważ jednak sam przyznałem "moja wina", postaram się jednak umieścić jakiś komentarz. Niech potem mnie krytykują i wytykają niewiedzę - trudno.

[pomruk]

OK, mój nieudolny komentarz:
W matematyce czy informatyce problem klasy P to taki problem, który można rozwiązać nawet dla dużej ilości danych w "sensownym" czasie - tzw. czasie wielomianowym. Czas potrzebny do rozwiązywania coraz to bardziej skomplikowanych problemów rośnie, ale nie w "przerażającym" tempie.
Natomiast problem klasy NP to taki problem, prawidłowość *rozwiązania* którego możemy sprawdzić w "sensownym czasie" - czasie wielomianowym.
Dla przykładu - sprawdzenie, czy liczby 3, 7, i 23 dają po pomnożeniu 483, jest problemem klasy NP. Ale rozłożenie liczby 483 na czynniki niestety jest trudniejsze. Trudność w mnożeniu coraz większych liczb rośnie umiarkowanie, w rozkładaniu - w stopniu przerażającym.
W miarę wzrostu liczby którą chcemy rozłożyć czas użyty na jej rozkładanie rośnie przy zastosowaniu współczesnych metod tak szybko, że możemy sobie "darować" próby takiego rozkładu dla dostatecznie wielkich liczb. Na złożoności owej opierają się nowoczesne metody szyfrowania, a więc ma ona ogromne znaczenie dla finansów, obronności, wszędzie tam gdzie potrzebna poufność danych.
Lecz nie jesteśmy jednak pewni, czy kiedyś tam nie udałoby się jednak opracować algorytmów, działających i w tym przypadku w "sensownym" czasie. Gdyby tak było, trzęsienie Ziemi w zastosowaniach matematyki murowane.
Pytanie to możemy wyrazić w postaci: czy P = NP? Czy zagadnienia, w których sprawdzenie rozwiązania wymaga "sensownego" wzrostu czasu przy coraz bardziej złożonych danych nie doczekają się - gdzieś tam, w przyszłości, choćby w teorii metod, w których czas poświęcony na rozwiązanie nie będzie również "sensownie" rosnąć?
Ten problem jest znany własnie jako problem P versus NP. Jest jednym z tzw. "problemów milenijnych" sformułowanych w 2000 roku. za rozwiązanie - milion dolarów nagrody.
Oczywiście, prób rozwiązania było wiele. Ja wspomniałem o ostatniej. Wg której P≠NP i wiele zagadnień praktycznie pozostanie nierozwiązywalnych.

[allegropajew]

I tu się panie pomruku nieco mylisz z tym łatwym sprawdzaniem. W wielu wypadkach tak jest, ale jak sprawdzić, że liczba jest pierwsza? Skąd wziąć świadka to łatwego sprawdzenia??????

Ano właśnie. Pratt pokazał dowód indukcyjny, bazujący na tym, że dla p pierwszego Z//pZ jest cykliczna (wtedy i tylko wtedy). Należy więc zgadnąć odpowiednie a < p i dla p1...pk

[speedyhawk]

Do kogo to napisałeś ?
Do siebie?

[allegropajew]

Ostatnie zdanie jest zrozumiałe raczej dla wszystkich. Należą się podziękowania.

Co do pierwszego akapitu, to głównie dla pomruka. Ale każdy wywnioskuje, że materia nie należy do arytmetyki szkolnej.

Gościula