| |||||
|
Próbujemy rozwiązać wielką zagadkę matematyki:
Jeśli czegoś nie da się zrobić, potrzebny jest ktoś, kto o tym nie wie i on to zrobi.
Nieformalny blog z przebiegu pisania pracy
Wesprzyj projekt:
Nieformalny blog z przebiegu pisania pracy
Film z mojego wystąpienia na konferencji TEDx Wrocław 2015, gdzie przystępnym językiem opowiadam o projekcie:
Zagadnienie "czy P=NP?" jest jedną z największych nierozwiązanych zagadek matematyki.
To pytanie, czy istnieje problem, którego rozwiązanie jest trudne do znalezienia, ale łatwe do zweryfikowania.
Clay Mathematics Institute
(USA) zaliczył ten problem jako jeden z siedmiu tzw. Problemów Milenijnych, a za rozwiązanie każdego z nich ufundował nagrodę w wysokości miliona dolarów.
VMPC: f(f(f(x))+1)
Od roku 2015 pracuję nad zapisaniem formalnego dowodu jednokierunkowości funkcji VMPC. Sam dowód tworzyłem na brudno w latach 2004-2015. Tak wygląda kompletny brudnopis zawierający wyniki mojej pracy. Nic wielkiego, ot słoik notatek:
Przełożenie tego na formalny język matematyki i zapisanie na czysto w pracy naukowej jest bardzo mozolnym i czasochłonnym zadaniem. Proces ten jest już jednak na ukończeniu. Praca na czysto ma obecnie ponad 70 stron A4. Zapisywanie głównego toku rozumowania zostało ukończone w połowie 2016. Od tamtego czasu trwa etap szlifowania pracy, którego dominującym elementem jest formalne uściślanie wszystkich użytych w dowodzie faktów dotyczących funkcji VMPC. Tutaj można znaleźć prowadzony przeze mnie od 2015 roku nieformalny blog z przebiegu pisania pracy. Dowód opisuje szereg zjawisk kombinatorycznych wynikających z konstrukcji funkcji VMPC, które pozwalają wyznaczyć maksymalną wartość prawdopodobieństwa, z jakim dowolny algorytm odwrócić funkcję. Jednocześnie prawdopodobieństwo to jest ekstremalnie niskie (ściślej - jest niewielomianowe, zgodnie z wymogiem definicji funkcji jednokierunkowej). Mówiąc ilustracyjnie, dowód określa maksymalną "wydajność" jakiegokolwiek algorytmu odwracania funkcji. Podobnie, jak nie możemy przekroczyć prędkości światła, tak żaden algorytm nie może odwrócić funkcji VMPC z wyższym prawdopodobieństwem niż to wykazane w dowodzie. Dowód ten, jeśli zostanie uznany za prawidłowy, będzie oznaczał rozwiązanie problemu "czy P=NP" przez wykazanie, że P ≠ NP, co jest konsekwencją istnienia funkcji jednokierunkowej. Funkcja VMPC byłaby pierwszą udowadnialną funkcją jednokierunkową na świecie, a rozwiązanie problemu "czy P=NP?" byłoby tylko (pozytywnym!) efektem ubocznym tego faktu. Więcej szczegółów: Jak przebiega obliczanie wartości funkcji VMPC Jak przebiega odwracanie funkcji VMPC Dla ekspertów: Formalna definicja funkcji VMPC i problemu jej odwracania Dotychczasowe praktyczne zastosowania funkcji VMPC: Funkcja VMPC leży u źródła całego projektu VMPC. Została zastosowana w Technologii Szyfrowania VMPC jako element algorytmu szyfrowania. Znalazła jednocześnie zastosowanie w aplikacji do szyfrowania danych VMPCrypt, która z tej Technologii korzysta. Na bazie funkcji VMPC powstała także gra Permutu. Mechanika gry w Permutu jest odzwierciedleniem procesu odwracania funkcji VMPC.
Pomagasz w ten sposób wykonać o jeden mały krok więcej w kierunku rozwiązania wielkiego problemu matematycznego "czy P=NP?". |
|
||||||||||||||||||
Copyright © 1999-2022 by Bartosz Żółtak
Aktualizacja: 06.12.2024 |