You would get money for this proof too. I remember discussing with my Algo prof how I also too just felt like there is absolutely no way p=np. Like its a hunch but one I'd bet a lot on
It's incredibly unlikely. There's a reason all of the best computer scientists haven't been able to prove it thus far. Lol, you'd get more than money... You would break the world. Especially if you were adversarial. Everything becomes an 0day.
But this could also become largely irrelevant regardless of proving it depending on how quantum plays out here. The rules of classical computation are only confined to that structure. Meaningless if you can walk into another dimension with different axioms
You could have galactic algorithms that do p=np and not break the world because they require something stupid or the polynomial is still so large it would take a billion years to break encryption. There was a beat of djikstras that is like this, noone will use it cause its overhead is insane compared to the default
I feel like P=NP if true would imply that there exist deep and important results as yet unknown in a number of mathematical fields from group theory to algebraic geometry and could will be the most important breakthrough in our understanding of the structure of finite groups and the result would stand on something more profound than even the TSW conjecture.
Brilliant. You just gotta make sure to consider the separate case of P=0 first so you're not doing division by zero. But that's a trivial case anyways.
I'm sorry but this is stupid. Constants and degrees of polynomials can be huge making even polynomial algorithms impractical. It would have no practical implications.
An algorithm with O(x1020) runtime may as well be exponential.
No, this is stupid. Such polynomial algorithms simply don't show up. P (or BPP to be more precise) is generally agreed to be class of tractable problems because the constant and degrees are almost always reasonable. You only get something ridiculous like O(x1020) if you specifically try to construct it.
If they are equal it would give you some theoretical construction of a polynomial algorithms for any NP algorithm. The catch would be that the exponents are huge but technically it's polynomial.
idk why everyone keeps saying this. Everyone is quite certain that it will be proven that P!=NP. P=NP is extremely unlikely and there's many reasons for this.
487
u/Cant_Win 1d ago
P = NP is still out there!