Czy P=NP rozsztrzygnięte?

0

Może ktoś już słyszał o Bartoszu Żółtaku:

Od 17 lat prowadzę niezależne badania naukowe, które mogą rozstrzygnąć (a na brudno już rozstrzygnęły) słynny, nierozwiązany od >dziesięcioleci problem matematyczny „czy P=NP”. Stanowi on jeden z siedmiu Problemów Milenijnych Clay Mathematics Institute z USA

Przydatne linki:
skrót historii
zbiórka pieniędzy
aktualności

Czy Waszym zdaniem jest coś w tym, czy może frajerzy wyrzucili ponad 25k złota na finansowanie cudzych urojeń? Osobiście, czytając aktualne wiadomości na froncie formalizacji dowodu, mam wrażenie, że facet nie posiada odpowiedniego przygotowania i aparatu pojęciowego aby zrealizować postawiony cel. Niestety, nie jestem specjalistą od matematyki. Może ktoś bardziej zorientowany zechce podzielić się swoją opinią?

0

Jak upublikuje dowód to sie przekonamy, ale ja jestem sceptyczny bo wiele tęgich głów już próbowało sie z tym zmierzyć. I to takich które mają na koncie sporo publikacji i odkryć z dziedziny teorii złożoności obliczeniowej. A tutaj jest niestety noname ;]

1

Już dziesiątki razy „udowodniono” równość i nierówność, jak dowód zostanie zweryfikowany, to wtedy będzie można ogłaszać przełom.
https://www.win.tue.nl/~gwoegi/P-versus-NP.htm

2

Jak czytam te jego aktualności, to za nic nie chce mi się z tego wyłonić sensowny obraz tego, w jaki sposób on chce tego dowieść. Pada na przykład takie stwierdzenie:

Polegało to na przebiciu się ponownie przez wyprowadzenie "kobylastego" wzoru, nad którym pracowałem na początku 2015 (wzoru na prawdopodobieństwo sukcesu pierwszego kroku odwracania funkcji VMPC).

Co wydaje mi się nieco nonsensowne i niepowiązane z problemem — nie rozumiem, co on ma. Jakąś funkcję, dla której pokazuje stochastyczną metodę odwracania jej? Ja przy takim dowodzie bym się spodziewał raczej języka teorii modeli czy teorii mnogości, nie odwołań do kombinatoryki (gdzie indziej pisze o tablicach różnicowych Eulera). Nie chcę tutaj uchodzić za takiego, co pozjadał wszystkie rozumy, ale gdy nie dostrzegam, co prezentowane informacje mają wspólnego z rozwiązywanym problemem, to nabieram sceptycyzmu co do tego, czy problem faktycznie został rozwiązany… Tak jak, nie wiem, gdybym udał się do mechanika z problemami z zapłonem, a on mnie próbował przekonać, że problemem były klocki hamulcowe…

Dalej, wpis z 27.10.2016:

A tu przykład z ostatniej chwili, jaką "siłę" upraszczania ma język opisu funkcji VMPC. Wiele zjawisk, których formalny zapis wymagał gimnastyki bez użycia języka (dotyczy to tej części pracy, która powstała przed jesienią 2015), teraz udaje zapisać w sposób elementarnie prosty przy użyciu tegoż właśnie języka.
27.10.2016

To akurat nijak nie świadczy o jakiejkolwiek wyjątkowości VMPC, każda dłuższa praca wprowadza swoje własne skróty, to jest rzecz trywialna…

Jak się do tego doda, że przekroczył pierwotny zapowiadany termin (jesień/zima 2016) i nie ma nawet brudnopisu na arXivie… Cóż, jestem sceptyczny. Bardzo.

Wg mnie to nie jest kwestia tego, czy on faktycznie czegoś istotnego dowiódł, lecz raczej czy on uczciwie wierzy (być może w wyniku zaburzeń psychicznych) że tak się stało, czy też cynicznie wyłudził od ludzi pieniądze.

0

@Althorion bo widzisz on to P != NP chce dowodzić trochę "przy okazji" a nie bezpośrednio. Generalnie on chce udowodnić że wymyślił funkcje jednokierunkową. Istnienie takiej funkcji faktycznie dowodziłoby automatycznie że P != NP.
Funkcje które potencjalnie mogą być jednokierunkowe są często stosowane w kryptografii -> faktoryzacja liczb, logarytm dyskretny.

0

Tutaj ładna czytanka w temacie;)

0

Dobra, może mi ktoś na chłopski rozum wyjaśnić, o co chodzi? Znalazłem coś takiego:

Hipoteza P≠NP to pytanie czy dla każdego zagadnienia, dla którego możliwa jest weryfikacja rozwiązania w czasie wielomianowym (dla zadanego problemu górną granicę czasu wykonywania danego algorytmu możemy matematycznie określić wielomianem pewnego określonego, ale stałego stopnia zależnym od danych wejściowych), możliwe jest również znalezienie tego rozwiązania w takim czasie?

Ale w żaden sposób nie mogę tego ogarnąć.

0

@Juhas: Wikipedia dość przejrzyście (imo), tłumaczy P vs NP.

[CIACH!]

0
Juhas napisał(a):

Hipoteza P≠NP to pytanie czy dla każdego zagadnienia, dla którego możliwa jest weryfikacja rozwiązania w czasie wielomianowym [...], możliwe jest również znalezienie tego rozwiązania w takim czasie?

Nie „dla każdego”, bo wystarczy znaleźć jedno takie zagadnienie.

0

@Azarien nie Dezinformuj, tak, wystarczy znaleźć jeden, ale NP-zupełny

[CIACH!]

5

@Juhas na chłopski rozum stosuje się pewne przybliżenia:

Mamy problemy werfyikacji oraz generacji i pytanie brzmi czy jeśli czas weryfikacji jest ograniczony wielomianem to czy czas generacji rozwiązania też jest ograniczony wielomianem. Jeśli dam ci n-liczb i spytam czy sumują się do 0 to w czasie liniowym mozesz mi udzielic odpowiedzi, bo po prostu dodasz te liczby. Ale jeśli dałbym ci pewien zbiór i powiedział zebyś z niego wybrał n-liczb które zsumują się do 0? Tutaj problem robi sie bardziej złożony. Naiwny algorytm były wykładniczy, bo po prostu dla każdej kolejnej liczby ze zbioru rozpatrywalibyśmy opcje "biorę" / "nie biorę", więc mielibyśmy na każdym poziomie 2 razy wiecej rozgałęzień.

Teraz co to w ogóle znaczy P i NP. To są problemy które da się rozwiazać w czasie wielomianowym (np. O(n), O(n^10)) odpowiednio na Deterministycznej Maszynie Turinga (P) oraz na Maszynie Niedeterministycznej (NP). Maszyna deterministyczna działa jak zwykły komputer, tzn podąża za jasno wytyczonym algorytmem, np. sumuje liczy z podanego zbioru i odpowiada czy wyszło 0.
Maszyna Niedeterministyczna działa podobnie, ale jest w stanie w pewnym sensie "zgadywać" którą ścieżkę wybrać (lub też tak jakby prowadzić równoległe obliczenia na wielu ścieżkach jednocześnie). Czyli jak w naszym przypadku powyżej, Maszyna Niedeterministyczna może "zgadnąć" czy daną liczbę zaliczyć do zbioru który zsumuje się do 0 czy też nie (albo analogicznie, może prowadzić równolegle obliczenia dla obu ścieżek i na koniec stwierdzić która była poprawna).

Wielkie pytanie brzmi: P=NP czy P!=NP. Bo o ile intuicyjnie niedeterministyczna maszyna wydaje sie dużo mocniejsza, to nie ma dowodów na to, że potrafi faktycznie rozwiązać wiecej niż maszyna deterministyczna w czasie wielomianowym.

Jest tu też pewne "ryzyko", bo niektóre zagadnienia z dziedziny bezpieczeństwa komputerowego opierają się o założenie ze P!=NP. Łatwo zweryfikować czy hash twojego hasła jest poprawny czy nie, ale wygenerować hasło na podstawie hasha juz nie bardzo, Ale gdyby P=NP to może się okazać że oba problemy są wielomianowe ;)

2

OK, czyli to nie jest jednak taka bezsensowna dywagacja matematyków.

W swoim sercu to jest "bezsensowna dywagacja matematyków", tylko akurat ma też zastosowania praktyczne (ale wątpliwe - bardzo mało kto podejrzewa że P=NP, a nawet dowód że P=NP musiałby być konstruktywny żeby być w miarę praktyczny). Ale jest to bardzo ważny problem, i rozwiązanie go by sporo teoretyczną informatykę popchnęło do przodu. Niestety, jesteśmy bardzo daleko od rozwiązania go - nawet na dużo prostsze pytania nie potrafimy odpowiadać, a poważne badania w temacie P?=NP koncentrują się obecnie na znajdywaniu kolejnych metod którymi nie da się rozwiązać tego problemu :P.

A pytanie poboczne, czy maszyną niedeterministyczną może być sieć neuronowa, czy algorytm genetyczny, czy to jest uważane za fizyczny sprzęt? - Juhas 22 minuty temu

Nie, to nie do końca ma sens. Niedeterministyczna Maszyna Turinga to pewna abstrakcja, której się nie da zbudować w świecie rzeczywistym. Można w uproszczeniu (błędnie) powiedzieć że to coś w rodzaju komputera który ma nieskończoną ilość procesorów, i za każdym razem kiedy normalny komputer musiałby podjąć decyzję, zamiast tego symuluje obie możliwe ścieżki.

Wielkie pytanie brzmi: P=NP czy P!=NP. Bo o ile intuicyjnie niedeterministyczna maszyna wydaje sie dużo mocniejsza, to nie ma dowodów na to, że potrafi faktycznie rozwiązać wiecej niż maszyna deterministyczna w czasie wielomianowym.

Dodam jeszcze to się może wydawać oczywiste (silniejszy model obliczeniowy może więcej, analogicznie jak intel i7 może więcej niż pentium 4), ale w matematyce nie wszystko jest takie jak się wydaje :P. Na przykład PSPACE = NPSPACE (analogiczne klasy złożoności, ale licząc pamięć a nie czas).

0

Nawet jest dość ciekawy film w temacie , ostrzegam uczciwie, straszna "strzelanka" ;)

[CIACH!]

0

OK, czyli to nie jest jednak taka bezsensowna dywagacja matematyków. A pytanie poboczne, czy maszyną niedeterministyczną może być sieć neuronowa, czy algorytm genetyczny, czy to jest uważane za fizyczny sprzęt?

@Juhas nie za bardzo bo taka sieć neuronowa czy algorytm genetyczny to jest raczej zwykła Deterministyczna Maszyna, bo przecież w każdym kroku wiadomo z góry co zostanie wybrane. Nie ma tam nigdzie miejsca na niedeterminizm.
Wyobraź sobie że idziesz przez labirynt i dochodzisz do rozwidlenia. NDT potrafi "zgadnąć" która ścieżka prowadzi do wyjścia, bez żadnych dodatkowych przesłanek.

1

Warto być może dodać, że sam podział na „szybkie” i „wolne” algorytmy nie jest tożsamy z tym na takie o złożoności wielomianowej i inne.

Bo załóżmy nawet, że P = NP i udało nam się tego dowieść w przedziwnie magiczny sposób — konstruktywnie (tzn. nie tylko wykazaliśmy, że algorytm o złożoności wielomianowej musi istnieć, ale nawet go znaleźliśmy dla każdego potencjalnego problemu). Tyle że on ma złożoność, powiedzmy, O(n^(G_64)), gdzie G_64 jest liczbą Grahama.
Jest wielomianowy? No jest. Jest użyteczny? Nie bardzo…

Tak więc ja bym się raczej upierał, że ten problem to jest taka „bezsensowna dywagacja matematyków”, jako że właściwie nie ma szans, że odpowiedź ich satysfakcjonująca będzie miała jakiekolwiek znaczenie praktyczne.

0

@Althorion tak ci sie tylko wydaje bo myślisz w małej skali. Notacja O ma jakikolwiek sens tylko jeśli myślimy o n->nieskończoności. Zresztą dla wielu matematycznych konstrukcji też mamy warunek, że zależność jest spełniona dla dowolnego n większego od pewnego ustalonego n0.
Bo nawet to twoje O(n^(G_64)) będzie znikome w porównaniu z O(n!) czy O(2^n) dla odpwiednio dużych n.

nie ma szans, że odpowiedź ich satysfakcjonująca będzie miała jakiekolwiek znaczenie praktyczne.

No, kilkadziesiąt lat temu też tak niektórzy narzekali że po co tyle kasy idzie na badania nad komputerami skoro zajmują całe pietra a liczą wolniej niz 4-latek. A jednak troche od tego czasu sie rozwinęło. Analogicznie, dziś może faktycznie dla odpowiednio dużego wielomianu nie zrobi nam różnicy jeśli P=NP bo i tak będzie to nie do policzenia, ale za kilka lat może być zupełnie inaczej.

0

@Shalom
Myślę w małej skali, bo problemy informatyczne są w małej skali. W praktyce nigdy nie rozważa się skalowania do nieskończoności. Jak robisz, nie wiem, serwis internetowy, to myślisz o tym, by mógł obsłużyć sto, tysiąc, milion, miliard jednoczesnych użytkowników, ale na tym się zatrzymujesz. Nie myślisz co będzie dla tryliona na przykład, bo to w praktyce bez sensu.

A to moje O(n^(G_64)) faktycznie będzie znikome w porównaniu do O(2^n) dla pewnych wartości n, ale te wartości są… nie do opisania ogromne. Nawet gdyby to było samo O(1) (o jak fajnie, złożoność stała!), tylko ze stałą G_64. Bo ta liczba wyżyna mózg na drugą stronę przy próbie zrozumienia, jaka jest wielka. Liczba możliwych uporządkowań cząstek elementarnych we Wszechświecie nawet nie zaczyna się do niej zbliżać.

No, kilkadziesiąt lat temu też tak niektórzy narzekali że po co tyle kasy idzie na badania nad komputerami skoro zajmują całe pietra a liczą wolniej niz 4-latek. A jednak troche od tego czasu sie rozwinęło.

To jednak zupełnie inny kaliber problemu. Nawet jakbyśmy mówili o tym algorytmie ze złożonością stałą, to samo przegonienie licznika od zera do G₆₄ by wymagało więcej energii niż ma cały nasz Wszechświat. To nie jest skala problemów inżynieryjnych, tylko takich, dla których musielibyśmy budować komputer z czego innego niż materia gdzie indziej niż u nas we Wszechświecie.

Dość powiedzieć, że jeśli oznaczymy sobie przez g googleplex, czyli 10^(10^100) i będziemy pisać g^g^g^g^g…, to nawet jeśli te g będą rozmiarów pojedynczych atomów, to braknie nam tychże w całym obserwowalnym wszechświecie by zapisać liczbę Grahama.

Dlaczego więc wziąłem taką ogromną liczbę? Bo to jest rozwiązanie innego matematycznego problemu, tw. Grahama-Rothschilda. I powinno stanowić pewną przestrogę co do tego, co w matematyce jest satysfakcjonującym rozwiązaniem.

EDYCJA:
Dosyć plastyczne przedstawienie tego, jak bardzo absurdalnie wielka jest ta liczba: http://waitbutwhy.com/2014/11/1000000-grahams-number.html

0

Najnowszy cytat ze strony: http://www.vmpcrypt.pl/aktualnosci.php

Pasujący do mojej płyty głównej 8-rdzeniowy procesor AMD FX-8320E (kosztujący 530 zł) pomógłby przyspieszyć symulacje 3-krotnie, jednak nie mogę sobie pozwolić na jego zakup.

Gość rozwiązuje największą zagadkę wszechczasów, nie może ogarnąć sobie procka za 530zł.
Beka.

2

Hm rzuciłem okiem na ten nowy news i generalnie jestem zawiedziony bo chłop miał dowodzić ze funkcja jest nieodwracalna a on tam jakieś prawdopobieństwa wyznacza i jeszcze empirycznie "na pałe" parametry chce wyznaczać symulacją, czyli generalnie podpucha.
Dowodów "probabilistycznych" na P vs. NP juz trochę było. Były też już dowody probabilityczne dla pewnych twierdzień, które miały 99% szans poprawności a okazywały się błędne.

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