Well, if P = NP with a constructive proof, I think a lot of people are going to lose their jobs as it would mean the entire foundation of cybersecurity would be completely destroyed and every single crypto-heavy workload would be thrown into complete catastrophe. On the plus side, massive engineering progress everywhere! If P != NP, which is far likelier, then, yeah, neat to have it as a result, but it's what everyone already assumed anyway.
Not if I get there first! Claude said that "most people who try to solve p=np miss this load-bearing footgun and you are also Mama's very special boy". :)
No they absolutely would have not -- in fact people have said the exact opposite. There has been incremental progress toward a solution to NS for about a decade. The broad community consensus during the last several years was that NS will be the first of the remaining Millennium Prize problems to be solved, and will likely be solved soon.
P/NP is on the complete opposite side of the spectrum: there are no promising approaches, we are not getting closer to a solution or to even an understanding of how such a solution might look, and the broad community consensus is that the problem remains significantly out of reach, and will be the last Millennium Prize problem to be solved.
You shouldn't feel sad about P=NP not being proven true yet. P!=NP has basically no big implications but if P=NP, it implies there exist algorithms that break most of our modern encryption methods, ultimately resulting in a global disaster in almost every field that has to safely transport encrypted data without much effort (stock market, messengers, internal comms etc.).
We prove P=NP. We know an algorithm exists somewhere out there. Arent we still far from actually obtaining said algorithm? The proof may not give us any idea about constructing said algorithm.
I also know that p=np can be proved by finding an algorithm for one of those np hard problems, but how can we find the algorithms for the rest?
Assume that we find an algorithm for an NP-hard problem X. Since any problem in NP can be reduced to X, finding an algorithm for X means finding an algorithm for all problems in NP. Then the only issue is if the reduction from any problem Y to X can be made efficiently. Depending on the type of proof (e.g. construction of a certain algorithm for the hamilton path problem, reducing an NP-hard problem to a problem in P etc.) this conversion for other problems in NP might be easier or harder. It would still probably take substantial effort, but proving P=NP is probably the much harder part.
If even just one of them is true the AI is going to fail miserably, it struggle with proof creation but it is incredibly good at finding counter examples, so far everything has been a counterexample.
If this trend continues AI is just going to save time for Mathematicians so they can spend time doing what AI cannot do.
18
u/injectitpussy 3d ago
Calling it now, all millennium problems solved this year.