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ć.
krok 3) 4+1=5: Ten prosty krok jest najważniejszy. F(F(1))+1 = 5
krok 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).
Permutrix
to gra polegająca na uzupełnianiu tabeli liczbami.
Jej zasady wywodzą się bezpośrednio z funkcji VMPC, a dokładniej z procesu jej odwracania.
Granie w Permutrixa to nic innego jak odwracanie funkcji VMPC i zapisywanie kolejnych
kroków tego procesu w tabeli.
Przedstawienie funkcji VMPC w postaci tabeli Permutrixa może pozwolić
jeszcze łatwiej zauważyć szczególne własności funkcji, które pozwolą udowodnić jej jednokierunkowość.
Problem można sprowadzić do pytania:
dlaczego Permutrixa (o odpowiednio dużych rozmiarach)
nie da się rozwiązać bez zgadywania liczb i dlaczego ilość zgadywanych liczb
rośnie ze wzrostem rozmiarów Permutrixa?
Celna i niepodważalna odpowiedź na to pytanie może być krokiem milowym w kierunku udowodnienia
jednokierunkowości funkcji VMPC, a tym samym rozwiązania problemu "czy P=NP".
Narodowa burza mózgów!
Zagraj w Permutrixa i napisz nam, co myślisz o jego rozwiązywaniu! To Twoja obserwacja,
nawet jeśli Tobie wydaje się oczywista, może pomóc rozwiązać problem "czy P=NP"!
Osoby, których opinie pomogą rozwiązać problem, zostaną wymienieni w publikacjach naukowych.
Jeśli chcesz podzielić się swoimi obserwacjami na temat rozwiązywania Permutrixa,
możesz to zrobić przy pomocy
formularza na dole tej strony.
2) On inverting the VMPC one-way function, Kamil Kulesza, University of Cambridge.
Informacja,
cała praca.
3) On inverting the VMPC one-way function, Kamil Kulesza, Wystąpienie na seminarium
Zakładu Złożoności Obliczeniowej i Algorytmów Instytutu Matematycznego Uniwersytetu Wrocławskiego, 21.05.2008.
Informacja.
4) Funkcja jednokierunkowa VMPC i system uwierzytelnionego szyfrowania VMPC-Tail-MAC
praca naukowa opublikowana na Krajowej Konferencji Zastosowań Kryptografii
Enigma 2004,
10-13 maja 2004, Warszawa.
5) Funkcja jednokierunkowa i szyfr strumieniowy VMPC, Bartosz Żółtak. Seminarium Kryptologiczne w Instytucie Matematycznym Polskiej Akademii Nauk, sala 106, Warszawa, 18.03.2004.
Informacja.
6) Funkcja jednokierunkowa i szyfr strumieniowy VMPC, Bartosz Żółtak, artykuł w magazynie komputerowym
SOFTWARE 2.0 (obecnie Software Developer's Journal).
numer 9 (117), wrzesień 2004, strony 26-29. Okładka magazynu.
Każda pomoc jest dla mnie bardzo cenna i z góry za nią dziękuję.
Jeśli chciałbyś jako firma, instytucja lub osoba prywatna stać się sponsorem tego projektu i
zostać wymienionym jako sponsor na stronie projektu, jestem także zainteresowany.
