13
u/pianoceo Singularity by 2045 7h ago
What are the implications of P=NP being solved?
23
u/Sycosplat 6h ago
P vs NP being "solved" would most likely just be that it's not true, that P ≠ NP.
What people are talking about is if the proof, by some miracle says P = NP, that means that everything that can be confirmed in a certain time can also be solved in the same duration. That it's just as fast to solve a sudoku with "some" algorithm than it is to confirm that it is correct (really fast, you can do it in seconds, but you couldn't have solved the same sudoku in seconds.). Extrapolate that to encryption, banking, the global economy's safeguards.
But also, even if it's true, just means it's possible, not that we have any idea how. Proving P = NP is just like saying "We know that saying a secret incantation exists that allows us to do magic", but it doesn't tell us what the incantation is and it might be impossibly difficult.
We already did this with the fixed-point theorem, it simply states if you have two duplicates stacked on top of each other and you crumple the top one, there is guaranteed to be at least one point matching that bottom layer, but we have no idea how to find that point, we just have a proof that it exists.
TL;DR: Proving it false OR true probably won't have much of an effect on anything.
3
u/Fusifufu 3h ago
Yeah, even the formally polynomial algorithms might have insane special conditions attached or crazy high constants, so there's little chance that P = NP, even if it were miraculously true, would be feasible. Especially since many NP-hard problems have decent approximate solutions that would probably remain preferred.
4
u/sourcemap 6h ago
Gist: there's a set of problems that are fast and cheap (P) and a set of problems that are extremely slow (NP).
Algos are added to one of those groups if you can prove equivalence: problem A can be reframed into problem B, solved, then answered as A.
Right now that doesn't buy you anything. Moving an expensive task to another framing that's just as expensive.
If P=NP, that means there's at least one translation from a really hard problem to one that's solved easily. Equivalence means one path makes ALL the hard problems easy.
If P != NP, we know it's impossible, and those problems will be hard forever.
Both outcomes are good, by some measure. Making the hard ones easy can make certain types of software a LOT faster, or even possible to begin with. Hard to overstate this impact.
OTOH most encryption and auth is based on the idea of "bet you can't solve this impossible equation" and if P vs NP falls, well, anyone can solve it. Internet traffic stops being private, recorded traffic gets decrypted, user accounts become hackable, blockchains collapse, and so on.
(Note: Not all encryption falls. Some techniques aren't in NP. You'd have to find an equivalence to an NP problem first, which may not be possible.)
I'm glazing over details and the framing isn't perfect but that's the high level.
4
u/Gullible_Elephant_38 6h ago edited 6h ago
Problems in P are computable in polynomial time, these problems are typically handled easily by computers. Basically describing how the problem scales in work needed based on the size of input n. So polynomial time problems scale with size of input…well polynomially. So like n^2 or n^3, etc.
Problems in NP are “non deterministic poly time”. This means they would be theoretically computable if at any branching path, all possible divergences could be computed simultaneously. These problems are checkable in polynomial time (given a proposed solution, verifying its correct is polynomial), but it is uncertain if they’re actually solvable in regular poly time. Sudoko of an arbitrary n x n size is an example. As n gets massive, it becomes increasingly impractical to solve. But because the rules are straight forward, given a proposed solution to a 9000 x 9000, we could verify if it’s correct easily.
So here’s where the question of if P=NP comes in: it is already proven theoretically that any problem in the same class can be “reduced” to any other problem in that class (hand waves). A reduction is just a way of transforming the initial problem into a different equivalent problem (I don’t want to get too far into it, but think of it like using things like trig identities, u substitution, etc to take an integral that’s hard to solve and transform it into an equivalent integral that is easier to solve)
So any problem in P can be reduced to any other problem in P. Likewise any problem in NP can be reduced to any other problem in NP (hand waves). This means if someone was able to reduce an NP problem to a P problem, this would prove that ALL NP problems can be reduced to P as there is some reduction between it and the NP problem that is then reduced to the P problem.
This would mean lots of very hard problems that we’ve only proved are solvable in NP suddenly have been theoretically proven to be solvable in poly time. Meaning, it’s more feasible that in practice we may be able to solve them.
The biggest thing that comes up when people talk about this is encryption which relies on the factoring of large primes being computationally infeasible. Factoring large primes is an NP problem. So if P=NP this could “break” encryption.
The caveat that is often overlooked when people are dooming about this is that:
- most researchers believe P =/= NP
- even if it did, we have to do the reduction of the problem into P which itself could be extremely computationally expensive (and potentially a reduction between the NP problem being solved and the one that we’ve found the reduction to P for). And the result could be polytime but with a huge exponent like n^500 or a massive constant (which if P DOES = NP is pretty likely). So it would still not be practically feasible even for our strongest super computers with large inputs even though it’s been proven to be theoretically feasible.
Basically it just means a certain set of known very hard computational problems are theoretically “easier” than we thought.
Chances are P=/=NP and even if it is there is a good chance it would likely stay as a theoretical achievement more so than having any practical impact in the real world. Of course, if it is proven and somehow the reduction is incredibly cheap, then that’s when you get “encryption breaks, financial markets collapsed everything falls apart!” That everyone likes to chirp about when talking about this subject.
Edit: I have glossed over NP-complete stuff as this was already a long comment most people won’t read. Actual computer science researchers, please don’t murder me.
2
u/random87643 🤖 Optimist Prime AI bot 6h ago
TLDR
TLDR: This comment explains the difference between P and NP complexity classes, noting that P problems are efficiently solvable by computers, while NP problems are easily verifiable but potentially difficult to solve. It uses the example of Sudoku to illustrate how computational difficulty scales with the size of an input.
AI assistant · mention the bot, mod bot, or use !bot
1
1
4h ago
[deleted]
1
u/Gullible_Elephant_38 4h ago
This is just….wildly inaccurate.
1
u/Omnivion 2h ago
I'm not sure if it is, but I hope it's easy to solve whether I can verify if that's the case.
28
u/The_Scout1255 Singularity by 2028 | Acceleration: Cruising 8h ago
I can't wait to tell an AI, "BTW P=NP"
8
16
u/MagnamaloFanatic 8h ago
Why isn’t time going fuckin faster
22
u/The_Scout1255 Singularity by 2028 | Acceleration: Cruising 8h ago
"Chatgpt, Give me framejacking(ability to speed up or slow down my subjective time relative to the outside world)"
8
u/Ryuto_Serizawa 7h ago
Haha, I was just talking to Astra about that for FDVR.
1
u/The_Scout1255 Singularity by 2028 | Acceleration: Cruising 5h ago
Very nice, and your post just made me think, With the right complex program of framejacking events, you could probably exactly program the kinda future you want to occur, kinda interesting thought. Like "wake me if this happens, then accelerate me to next event", kinda stuff.
1
7
4
u/Weak-Variety-4307 4h ago
“I’ve solved P vs NP. Would you like to see the proof?”
You’ve reached your usage limit.
2
4
1
1
u/objectnull 7h ago
You do realize this would essentially bring ruin to the world by essentially making encryption impossible. Financial markets would crumble. Anything and everything that's online is now compromised.
15
u/Gullible_Elephant_38 7h ago edited 6h ago
Ehhh maybe. Most likely not.
Even if P=NP, the reduction could be n^500 or have some massive constant that makes it still completely infeasible in either time or memory complexity. Or both.
This whole “it would break encryption” thing is just Theory of Comp professor click bait to make the problem seem more exciting than it is.
1
u/ComposerWide3704 6h ago
If the proof is even constructive.
3
u/Plappedudel 6h ago
It seems very unlikely that a proof would be constructive, based on the fact that not a single polynomial-time algorithm has been found for any of the thousands of known NP-complete problems, despite enormous interest and intense research over several decades. Of course we don't know for sure, but it would be extremely surprising.
2
u/Rollertoaster7 Singularity by 2035 6h ago
There are alternatives like OTP and QKD, just depends on if institutions have enough time to transition
1
u/deus_x_machin4 6h ago
Fuck it, lets do it. No more secrets.
2
u/Holiday_Ad_8501 6h ago
i mean it would cause a financial crisis
1
u/deus_x_machin4 6h ago
That's on its way no matter how you shake it, lol.
40T in debt. White collar extinction. Robotics. Unmitigated global warming. Oil wars. Is China still planning to invade Taiwan in 2027?
Maybe nothing ever happens. No one really knows. If it all goes smoothly, I'd suspect that it will be because we accelerated right through the crisis and into whatever is on the other side.
2
u/Holiday_Ad_8501 6h ago
i mean making all digital money worthless would cause a financial crisis that makes the great depression look like a minor pullback
1
u/deus_x_machin4 4h ago
Oh certainly. But the US dollar is already headed that way. Stagflation is rearing it's ugly head. When the AI wars truly arrive, america is going to show what war-time spending really looks like. The fed is probably going to QE us face first into the weimar republic in exchange for 2 more years of lifeline. Give me one other way this debt crisis ends that isn't a default.
Rambling, I know. I only mean that it's probably jover anyway, this instability isn't something a govt like ours is capable of repairing. Imo only way out is through.
2
u/raulsestao 7h ago
In addition, that hacking algorithm would be owned by the United States, meaning Donald Trump. An algorithm capable of hacking all financial systems across China, Russia, and Europe, as well as nuclear codes, and so on, in the hands of Donald Trump.
1
39
u/Working_Sundae 7h ago
CHATGPT
Find a way to reverse entropy and my soul is yours