The P vs NP problem is a question if
there exist problems which solutions are difficult to find but are easy to verify.
For decades no such problem has been discovered but also it hasn't been proved that such problems don't exist...
Theoretically inverting a one-way function would be such a problem.
A one-way function is a transformation, which is easy to perform (it is ease to compute its value
for an argument) but difficult to invert (find the argument which produced a given value).
However it is not clear whether one-way functions exist...
If one was found, the great secret would be solved and we would determine that
P is not equal NP.
In 1999 I discovered a function which I called "VMPC".
In 2004 I was invited to present it on the international cryptography conference, FSE.
In 2006 a paper analysing this function was published at the Cambridge university.
The function has two distinctive features: it is exceptionally simple and, according to
all the knowledge I am aware of, it is a one-way function.
For the function to be officially called "one way" a
mathematical proof of its one-wayness is necessary.
The attempt to build such a proof is the purpose of this project.
"Nobody has ever proved one-wayness of any function so it will not happen here either" - this is the rational view of the project's chances.
However we are so passionate about the VMPC function that we devote a lot of energy to keep trying.
step 3) 4+1=5: This simple step is the most important. F(F(1))+1 = 5
step 4) 5 gives 2: V(1) = F(F(F(1))+1) = 2
We have just computed the first element of the VMPC function: F(F(F(1))+1)=2.
The above four steps need to be repeated for the remaining four values of 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 instead of 6 because there are only numbers from 1 to 5 in this permutation).
We obtain that the value of the VMPC function for permutation F is (2,5,3,4,1).
Permutrix
is a game which purpose is to fill a table with numbers.
Its rules are derived straight from the VMPC function. More precisely - from the process of inverting the function.
Playing Permutrix is nothing else than inverting the VMPC function and writing the steps of the process in the table.
Presenting the VMPC function as a Permutrix table can help notice some specific properties of the function
which could help prove its one-wayness.
The problem can be summarised in a question: why Permutrix (of sufficiently big size)
cannot be solved without guessing some numbers and why the quantity of the guessed numbers
grows along with the growth of Permutrix size?
A precise and unquestionable answer to this question could be a milestone
improving the one-wayness of the VMPC function and therefore solving the P vs NP problem.
The brainstorm!
Play Permutrix and write to us what you think about solving it! Your observations, even if obvious to you,
can help solve the P vs NP problem!
People whose opinions will help solve the problem will be mentioned in the scientific publications.
If you would like to share your observations about solving Permutrix you can do it using the
form at the bottom of this page.
2) On inverting the VMPC one-way function, Kamil Kulesza, University of Cambridge.
Information,
whole paper.
3) On inverting the VMPC one-way function, Kamil Kulesza, presentation on a seminar,
Mathematical Institute, Wroclaw University, Poland, 21 May 2008.
Information.
4) VMPC One-Way Function and Stream Cipher - presentation on a seminar,
Mathematical Institute of Polish Academy of Sciences (IM PAN)
on 18 March 2004, Warsaw, Poland.
5) VMPC one-way function and VMPC-Tail-MAC authenticated encryption scheme - Presentation of a paper on the
Cryptography Applications Conference
Enigma 2004,
10-13 May 2004, Warsaw, Poland.
6) VMPC One-Way Function and Stream Cipher - article published by a computer magazine
SOFTWARE 2.0 (currently Software Developer's Journal)
issue 9 (117), September 2004, pages 26-29. See magazine cover.
or by bank transfer to our account:
IBAN: PL50 1020 5558 1111 1331 4210 0053
Bank name: PKO BP SA
Bank's SWIFT code: BPKOPLPW
Country: Poland (Europe)
Any help is very valuable for me and I thank for it in advance.
If you would like - as a company or a private person become a sponsor of this project
and be mentioned on this website as a sponsor, I am also interested.
