Harry Potter, P versus NP and time travel
Sorry for the clickbait of a title.
Disclaimer: Might contain HPMOR spoilers.
In the last KopiJS session, I came to know about Harry Potter and the Methods of Rationality. It’s a fanfic based on HP universe. I’m not a fanfic kind of guy but after seeing Thameera, Chanux and Gaveen fan-boying, I decided to put aside The Sound and the Fury for a while and start reading HPMOR.
It’s a page turner. Insanely fun to read and far better than the original series (I’m already seeing die-hard HP fans waving pitchforks).
Harry is a rationalist. His father (uncle, rather) is a professor in biochemistry. Harry is well versed in scientific literature. He has read Godel, Escher, Bach and Judgment Under Uncertainty: Heuristics and Biases and volume one of The Feynman Lectures on Physics. He’s no ordinary 11 year old.
In chapter 17 of the book (the one I just finished reading) he comes up with an algorithm to find the factors of a product of 2 prime numbers.
Generating a product of two sufficiently large prime numbers is an important step in key generation of public-key cryptography.
If you can decompose such a product into its factors in polynomial time, congratulations you have broken RSA.
RSA is least of your concerns when you can time travel and below algorithm is not to be taken seriously.
Here goes:
1) Get two prime numbers of known digit length (3 for example), p and q and get the product n at a time x. (p and q are unknown to you)
2) Write 101*101 on a paper.
3) Go back in time to time x and give the paper to yourself. (Using a time-turner, remember that thing Hermione wore around her neck in Prisoner of Azkaban?)
4) Your past self calculates the product.
5) If product == n, return p, q
6) If product != n, increment q by 2. Go back to time x and give the paper to your past self.
7) If product !=n and q > 997, increment p by 2. Go back to time x and give the paper to yourself.
8) If p > 997 and q > 997 and product != n, send an empty paper to your past self.
With this algorithm Harry had just shown P=NP given that you can time travel.
P versus NP is probably the most important unsolved problem in computer science. It is one of the seven millennium prize problems. A proof that P=NP would have immense consequences and probably will change the internet as we know today. Our current implementations of Public-key cryptography will have to be changed. Computer Vision and Voice Recognition fields would be able to make a giant leaps. It would revolutionize mathematics to name a few.
Check the movie Travelling Salesman.It talks about the implications of proving P=NP.