Próbujemy rozwiązać wielką zagadkę matematyki:
projekt badawczy "Funkcja jednokierunkowa VMPC - czy P=NP?"

Jeśli czegoś nie da się zrobić, potrzebny jest ktoś, kto o tym nie wie i on to zrobi.
Albert Einstein.

Nieformalny blog z przebiegu pisania pracy

Wesprzyj projekt:

www.zrzutka.pl/vmpc


Permutu to gra planszowa wywodząca się z funkcji VMPC.



Harmonogram projektu:

• Dopracowanie szczegółów pracy dowodzącej jednokierunkowości funkcji VMPC.
  
  
• Publikacja w międzynarodowym czasopiśmie matematycznym.
  
  
• Weryfikacja wyników przez Clay Mathematics Institute.

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.

Przez dziesięciolecia nie znaleziono żadnego takiego problemu. Ale i nie udowodniono, że nie istnieje.

Jednym ze sposobów na rozwiązanie zagadki jest odkrycie funkcji jednokierunkowej - przekształcenia, które jest łatwo wykonać, ale którego nie da się odwrócić. Innymi słowy, znając wartość funkcji, nie da się znaleźć liczby (ściślej - argumentu), z jakiego ta wartość powstała.

Otoczeni jesteśmy przez funkcje niejednokierunkowe. Dla przykładu - jak odwrócić funkcję +1? Jeśli nawet czytelnikowi, który nienawidzi matematyki, powiem, że wartość tej funkcji to 11, to i tak odejmie on jedynkę od 11 i uzyska prawidłowy wynik: 10. Wykorzystaliśmy tu (intuicyjnie) fakt, że odejmowanie jest funkcją odwrotną do dodawania. A teraz wyobraźmy sobie świat, gdzie po "dodaniu jedynki", nie jesteśmy w stanie potem tej jedynki odjąć... To jest właśnie świat funkcji jednokierunkowych.

Funkcja taka miałaby upragnioną cechę - rozwiązanie problemu (odwrócenie funkcji) byłoby trudne, ale zweryfikowanie rozwiązania (obliczenie wartości funkcji) byłoby łatwe. Istnienie takiej funkcji rozwiązałoby wprost problem "czy P=NP?" stwierdzeniem, że P ≠ NP.

Nie wiadomo jednak, czy funkcje jednokierunkowe w ogóle istnieją.

Dotychczas na świecie nie udowodniono jednokierunkowości żadnej funkcji. Niektóre funkcje (jak np. problem faktoryzacji liczb, będący fundamentem algorytmu szyfrowania RSA, stosowanego np. do podpisów cyfrowych) są uznawane za jednokierunkowe w praktyce - jeśli operują na gigantycznych liczbach, np. 100-cyfrowych - ale nawet wtedy nie ma formalnego dowodu ich jednokierunkowości.

W 1998 roku odkryłem nową funkcję matematyczną, którą nazwałem "VMPC". Zgodnie moją najlepszą wiedzą - jest ona właśnie funkcją jednokierunkową, której jednokierunkowość da się formalnie udowodnić.

W 2004 roku zostałem zaproszony do zaprezentowania funkcji VMPC na międzynarodowej konferencji kryptograficznej FSE w Indiach. Mój wyjazd na tę konferencję był współfinansowany przez Kancelarię Prezydenta Rzeczpospolitej Polskiej, Aleksandra Kwaśniewskiego oraz przez Prezydenta Wrocławia, Rafała Dutkiewicza.

Funkcja VMPC jest prostym przekształceniem permutacji wg następującego wzoru. Kluczowym jej elementem jest właśnie dodanie liczby 1, ale podczas składania permutacji (permutacja to tylko ciąg potasowanych liczb).

VMPC: f(f(f(x))+1)

Działanie funkcji VMPC można zilustrować na schemacie:

Więcej szczegółów:

Jeśli chcesz, możesz wesprzeć badania:

Rejestrując aplikację VMPCrypt za dowolną kwotę vmpcrypt.pl

Kupując grę Permutu permutu.pl

Kupując grę komputerową Urban permutu.pl/urban

Wdrażając Technologię Szyfrowania VMPC szyfrowanie.com

Pomagasz w ten sposób wykonać o jeden mały krok więcej
w kierunku rozwiązania wielkiego problemu matematycznego "czy P=NP?".