Isn't this dangerous? If it succeeds in proving P=NP, it could break the internet.<p>EDIT: from what I can tell, the answer is no, as long as we have faith in this very specific scenario where it turns out technically to be polynomial time, but the constants and exponents are huge. I don't have such faith :)<p>Of course maybe P≠NP and so there's no risk.
Consider the falsification of the Exponential Time Hypothesis. A counterexample demonstrated that that class of problems could be solved in less than exponential time, but "less than exponential" was still absurdly long, worse than any practical algorithms used today.<p>If we had a proof that P=NP because NP problems can be solved in O(n^(log*⁻¹ 100)) time ( <a href="https://en.wikipedia.org/wiki/Iterated_logarithm" rel="nofollow">https://en.wikipedia.org/wiki/Iterated_logarithm</a> ), that would still be an astounding logarithmic result, but would not be a practical threat to current systems that rely on NP-hard problems.
Other surprising results that still didn't change the course of computing forever: <i>anything</i> that can be computed in O(f(n)) time can also be computed in O(√f(n)) memory (but more time): <a href="https://blog.computationalcomplexity.org/2025/02/you-need-much-less-memory-than-time.html?m=1" rel="nofollow">https://blog.computationalcomplexity.org/2025/02/you-need-mu...</a><p>Proven by a human, too.
In particular, the algorithm that falsified the Exponential Time Hypothesis started something like this:<p>> First, if the number of variables has less than a million digits, solve the problem by brute force. Otherwise, ...<p>There is absolutely no chance an algorithm like this has any immediately practical consequences.
That would depend a lot on what exactly the proof shows. The consequences of a non-constructive proof that P=NP would probably be different than a constructive one that shows a specific low-order/low-constant-factor algorithm suffices.<p>And even then, it's probably better in the long run to secure the foundations of our tech.
P=NP doesn't do anything unless the algorithm is fast to compute.
There are several entities who would like to "break the internet" with the resources to run a lot more than 96 bots against this question. I doubt the world intelligence agencies are burning a lot of tokens against the Riemann Hypothesis, but I would bet a lot more tokens have been burned on this already than is publicly known about, and there's a non-trivial chance someone already has the answer to this question and just hasn't shared yet because they have no motivation to reveal capabilities.<p>Bear in mind P = NP doesn't instantly break the internet. NP being in P would be shocking enough on its own terms, but "nondeterminism is also of no <i>practical</i> value in solving a problem" would be yet again even another more shocking result. Really? NP is so thoroughly in P that even what is more-or-less <i>psychic knowledge</i> of the right answer isn't worth at least an O(n^3) factor of complexity reduction, if not more? If the reduction is anything less than O(n^2 and some logs here) I will be even more shocked than I would be to hear P = NP (since I'm on team P != NP), and that's the rough edge of where it would actually change the world. O(n^3) is already getting to be infeasible for a lot of real world problems; there's a reason we spend a lot of time talking about O(1) and O(n) and O(n^2) and rarely venture much farther beyond that, and even O(n^2) gets its own "accidentally quadratic" meme because of how often that is impractical too.
> P being in NP would be shocking enough on its own terms<p>P is definitely, trivially, in NP. You may have confused them for each other.<p>If any NP-complete problem is in P, then so is all of NP, because they can all be reduced to it. Out of the non-NP-complete problems, many of them are in NP but not in P, because it would immediately follow that P != NP and I would've heard about that. If we proved that one <i>was</i> in P, that would just mean that problem was in P.<p>So the only interesting proofs are either that some NP-complete problem is in P (proves P==NP) or that some NP problem, whether NP-complete or not, isn't in P (proves P!=NP).<p>And yes, everyone sane expects P!=NP, the alternative doesn't make much sense. It just hasn't been proven.
Thinko. I got it right later in the post.<p>Many sane people think P = NP. I am not aware of a survey that asks them how complicated the reduction might be, though. I do think a number of them believe and/or are concerned that we could end up with a non-constructive proof that NP is in P, which at least mathematically is arguably the worst possible outcome.<p>I think a lot of people would agree that naively it is obvious that P != NP. But if you spend time in the algorithms would you see your intuition about what the lower bound of some problem must be shattered over and over again, and the naive confidence gets shaken.
I think your last sentence is a bit strong. Knuth suspects P = NP, and has some fairly reasonable arguments against the notion that if all these well-known problems had polynomial-time solutions, we would have found one by now.
Obscurity only provides a false sense of security.
The danger was already accepted once systems started relying on it en masse, despite it not being proven nor disproven.<p>Avoiding to try figuring it out is a risk, not a mitigation of risk.
Isn’t this like saying you’d rather not get bloodwork done because if it turns out you have leukemia, you could die?
don't wait for a proof, just assume that P=NP and break the internet
The assumption is that a proof will be constructive - that it will contain a description of a method to solve NP problems in P time. Knowing what it is breaks the internet. You can't just assume it exists, still not know what it is, and execute it anyway.
I told Claude to assume P=NP and asked it to write a python script to deliver me everyone's Bitcoin. It didn't work.
This is like setting up an automatic object wall slammer because there's a quantum chance of phasing through it
Wir müssen wissen<p>Wir <i>werden</i> wissen
If P=NP we would be truly doomed, but this nevertheless shouldn't stop you researching it, no matter by human or AI.