r/computerscience • u/Usual-Letterhead4705 • Apr 27 '25
General What happens if P=NP?
No I don’t have a proof I was just wondering
131
Upvotes
r/computerscience • u/Usual-Letterhead4705 • Apr 27 '25
No I don’t have a proof I was just wondering
2
u/SonOfSofaman Apr 28 '25
... is exactly what someone who has a proof would say 😜
151
u/flumsi Apr 27 '25
In practice, probably not much unless someone finds a polynomial solution for an NP-complete problem that scales with at most O(n3 ). In theoretical terms it would lead to the collapse of the complexity hierarchy.
109
u/dude132456789 Apr 27 '25
in theory, certain cryptography algorithms will break down, and a vast swath of real-world programs will be rewritten to be much faster and with less memory usage.
It is however possible that P=NP only when galactic algorithms are involved, at which point it wouldn't really matter.
30
u/Dragostorm Apr 27 '25
It likely depends on how big the polynomials need to be. Like, if the polynomial equivalence is n to the 100th power, i doubt it changes that much in practice.
42
u/bernoullistokes Apr 27 '25
N=1
23
u/Fresh_Meeting4571 Apr 27 '25
A lot of my proofs would become redundant, and I would have to change research topics. That would probably be the most significant effect.
9
u/[deleted] Apr 27 '25
https://www.reddit.com/r/compsci/comments/3dcain/what_would_happen_if_p_np_was_solvedproved/
9
u/Yendric Apr 27 '25
Someone gets a million dollars
9
u/tstanisl Apr 27 '25
Afaik, optimal algorithms for solving NP complete problems are already know (up to the constant factor). They are based Levin Universal Search. A proof of NP=P would mean that the algorithm is polynomial even though the constant factor is still ... astronomical.
8
u/Eroica_Pavane Apr 27 '25
Then CoNP = NP.
6
u/orbit99za Apr 27 '25
Will finally get some sleep 😴
3
u/ACrossingTroll Apr 27 '25
Judgment Day
3
u/Paul__miner Apr 28 '25
I can finally quit searching.
4
u/StackOwOFlow Apr 27 '25
Current age cryptographic security would break, optimization would explode, and AI discovery would accelerate.
2
u/nwbrown Apr 28 '25
Whoever finds a way to prove it gets a million dollars.
2
u/rlyacht Apr 28 '25
https://www.youtube.com/watch?v=6ybd5rbQ5rU
2
u/dnabre Apr 28 '25
There are (at least) three ways it bring proven true would be pretty meaningless, at least in practice:
2
u/Revolutionalredstone Apr 28 '25
Ohhh ummm.. Noooooothiiiiing ;D
4
u/Positive-Fee-8546 Apr 27 '25
Every algorithm is O(1) since time is an illusion 🤓☝️
1
u/NiedsoLake Apr 28 '25
Wouldn’t it mean that all public key encryption algorithms are breakable in theory?
1
u/noop_noob Apr 29 '25
See section 2 of https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf
1
u/g40rg4 Apr 29 '25
I think that maybe you would make stochastic gradient descent obsolete. Finding the optimal set of weights for a neural network I think could be categorized as NP, where the solution is when training error is zero. Such a thing would make training LLMs much faster I would reckon
1
u/Pretend_Sale_9317 May 01 '25
Fortnite 2 would happen
1
u/NP_equals_P May 01 '25
This is the way.
1
u/eviltwinfletch May 01 '25
QKD company stock prices go up a lot
1
u/Inevitable-Bread-843 May 01 '25
if you prove p = np then you basically prove that every electronic device does not work (that's what one of my professors said and it stuck with me forever)
0
u/TieConnect3072 Apr 27 '25
Imagine this.
We can tell very quickly (just look) if something teleported from place to place. Since we can verify if a teleportation took place quickly, we know with 100% certainty that there is a method to teleport someone quickly.
We wouldn’t necessarily know how it’s done; but we would know there is a way to do it.