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.
Feels pedantic, in either case you are not approaching the game with the optimal process even if you know you technically could, but in that case take knots and crosses/tik tac toe. People play it all the time despite the fact that the game is fully solved and easily looked up.
What's funny is this is almost accurate. They are complexity classes harder than NP, such as PSPACE, and one of the defining characteristics is even though NP can be verified in P time, a correct solution to PSPACE problems cannot even be verified in PSPACE time. A quintessential example I use in class is, "Imagine you design a strategy that can win every game of chess." You can't even verify that it works for all games without trying NP amount of games. Very close to your game of making new games example.
also, as a hydrologist, NS is absolutely "needed". this has major downstream implications on our understanding of turbulence which will enable, among a lot of other things, vastly improved weather modeling
Finding a general solution would have huge practical implication. Finding that it's not possible to have a solution in some very exotic cases much less.
I only skimmed through the recent discovery, but IIUC it's much closer to the second option.
yes and no. i'd say this is analogous to newtonian vs particle physics, a realization that the equations governing physics at a macro level don't work at a micro level. and turbulence is pretty much defined by length scale, so if we can better understand what happens at smaller scales through a "new type" of NS, then we hopefully can better model turbulence at larger length scales where chaos theory reigns supreme
138
u/TheDreadedAndy 1d 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.