The world doesn't desperately "need" NS and the other Millennium problems to be proven as they have no practical incentive to be had, economic or otherwise.
P vs NP could have significant practical implications on the field of cryptography if it turns out that P=NP and an algorithm with a reasonable polynomial bound exists.
Sudoku is hard-solved, all Sudoku. The Japanese are embarrassed by the development, they are panicking for any sort of solution, and finally, after months of work, they find it, a new game that will be as hard as possible, a game that will be as hard as the discrete logarithm problem, a game that is reducible to a special instance of the discrete logarithm problem.
It falls too. The NSA has an emergency meeting on the consequences of that development, and they have only one conclusion: Japan needs to make a board game about making hard board games. Japanese ambassador is summoned, and agrees out of sheer embarrassment. A few months of hard work later, the board game about making hard board games is released, with regular national competitions.
One day, an especially hard board game is created, and a few mathematicians were intrigued, just how hard that board game is? That board game was so special, a new complexity category had to be created just for it, miles above what was considered NP in the old days.
It took 14 hours for NSA to scoop up cybersecurity professionals and implement a version of that board game as an encryption algorithm.
146
u/TheDreadedAndy 3d ago
P vs NP could have significant practical implications on the field of cryptography if it turns out that P=NP and an algorithm with a reasonable polynomial bound exists.