Projekt badawczy "Funkcja jednokierunkowa VMPC - czy P=NP?"

Cel projektu

Zagadnienie, czy P=NP, jest jedną z wielkich zagadek matematyki. To pytanie, czy istnieją problemy, których rozwiązanie jest trudne do znalezienia, ale łatwe do sprawdzenia. Clay Mathematics Institute z USA ufundował za jego rozwiązanie nagrodę miliona dolarów. Więcej o tym problemie można przeczytać np. na Wikipedii.

Problem “czy P=NP?” to pytanie, czy istnieją problemy, których rozwiązania są trudne do znalezienia, ale są łatwe do zweryfikowania.

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

Jednym ze sposobów na rozwiązanie zagadki byłoby odkrycie funkcji jednokierunkowej - przekształcenia, które łatwo wykonać ale trudno odwrócić. Nie wiadomo jednak, czy funkcje jednokierunkowe w ogóle istnieją… Gdyby jakąś odkryto, rozstrzygnęłoby to, że P jest różne od NP.

W 1999 roku odkryłem pewną funkcję, którą nazwałem “VMPC”. W 2004 roku zostałem zaproszony do zaprezentowania jej na międzynarodowej konferencji kryptograficznej FSE. W roku 2006 na uniwersytecie w Cambridge opublikowana została praca na temat tej funkcji.

Funkcję VMPC wyróżniają dwie cechy: jest bardzo prosta i zgodnie moją najlepszą wiedzą - jest funkcją jednokierunkową.

Aby mogła być oficjalnie uznana za jednokierunkową, potrzebny jest matematyczny dowód jej jednokierunkowości.

Próba zbudowania takiego dowodu jest celem tego projektu. - “Nikomu dotychczas nie dało się udowodnić, że jakakolwiek funkcja jest jednokierunkowa, więc tu na pewno też się nie uda” - tak należy racjonalnie ocenić szanse tego projektu.

jednakże mamy tak wielką pasję dla funkcji VMPC, że i tak poświęcamy dużo energii, żeby próbować.

Jak działa funkcja VMPC

Nazwa funkcji pochodzi z angielskiego: Variably Modified Permutation Composition (zmiennie modyfikowane złożenie permutacji). Funkcja VMPC to pewne przekształcenie permutacji (ciągu potasowanych liczb).

Weźmy przykładową 5-elementową permutację F=(3,1,4,5,2).

Funkcja VMPC przekształci ją w nową permutację V wg wzoru V(x) = F(F(F(x))+1)

  1. 1 daje 3: F(1) = 3
  2. 3 daje 4: F(F(1)) = 4
  3. 4+1=5: Ten prosty krok jest najważniejszy. F(F(1))+1 = 5
  4. 5 daje 2: V(1) = F(F(F(1))+1) = 2

Obliczyliśmy już pierwszy element funkcji VMPC: F(F(F(1))+1)=2. Powyższe 4 kroki powtarzamy dla pozostałych wartości x: F(F(F(2))+1)=5, F(F(F(3))+1)=3, F(F(F(4))+1)=4, F(F(F(5))+1)=1 (5+1=1 zamiast 6, gdyż w tej permutacją są tylko liczby od 1 do 5). Funkcja VMPC dla permutacji F ma więc wartość (2,5,3,4,1).

Dlaczego funkcja VMPC może rozwiązać zagadkę “czy P=NP?”

Odwrócenie funkcji z powyższego przykładu to następujące zadanie: mając dane VMPC(F)=(2,5,3,4,1) trzeba znaleźć F. Zadanie to okazuje się tak trudne, że część elementów szukanej permutacji F musi zostać zgadnięta! Zgadnięcie oznacza w praktyce przeszukanie wszystkich możliwych wartości zgadywanych elementów, aby trafić na te prawidłowe.

Gdyby udało się udowodnić, że zgadnięcia te są niezbędne, wówczas VMPC stałaby się pierwszą na świecie funkcją jednokierunkową, a zagadnienie, czy P=NP - rozwiązane.

Zgodnie z obecnym stanem mojej wiedzy, aby odwrócić funkcję VMPC dla 10-elementowej permutacji, trzeba zgadnąć 3 elementy permutacji F. Przeszukanie ich wszystkich możliwych wartości zajmuje około 120 operacji. Dla 30-elementowej - zgadnąć trzeba już 6 elementów i wykonać 16 milionów operacji. Dla 250-elementowej - zgadnięcia wymagają aż 33 elementy F, co oznacza 7000…000 operacji. To liczba mająca 75 zer. Wynosi ponad miliard miliardów miliardów miliardów miliardów miliardów miliardów miliardów (słowo “miliard” występuje 8 razy).

Ciekawostka, że niemal identycznie wyglądająca funkcja G(x)=F(F(F(x))), jest bardzo prosta do odwrócenia.

Nikt nie udowodnił jednokierunkowości jakiejkolwiek funkcji. Więc dlaczego wierzymy, że może to być możliwe dla funkcji VMPC?

Ponieważ VMPC jest tak prosta. Kilka linijek nienaukowego tekstu wystarczyło, aby wytłumaczyć Ci, jak funkcja działa…

##