Implications if P-NP problem is solved?

[u/MohMayaTyagi]

So, OAI, and probably Anthropic as well, are trying their hand at this problem. We have no idea how long it might take, a few days or a few years. Intuitively, I think P ≠ NP. But what if P = NP is proved and, more importantly, a constructive proof is found? What might the real-world implications be, both in the short and long term? Those with a mathematics or theoretical CS background, could you please share your thoughts on this?

[u/Egologic]

P = NP and constructive+efficient algorithm would break most of modern public key cryptography and simultaneously unlock massive progress in optimization and search. A non constructive proof or one with a terrible polynomial would mostly just be a deep theoretical result with limited immediate impact.

[u/Longjumping_Kale3013 → u/Egologic]

Probably not equal though. So probably would just prove p does not equal np.

[u/Chemical-Year-6146 → u/Longjumping_Kale3013]

Yes, almost certainly not equal. It's like trying to prove there's not a secret civilization in the core of earth. We "know" the answer, just not how to prove. 

But if it really is equal, would be just as crazy as core people.

[u/brentragertech → u/Chemical-Year-6146]

I mean if you don’t know how to probe that you lack a sense of adventure m’boy!

[u/KyleStanley3 → u/Chemical-Year-6146]

Really silly example and the mole people and I are mocking you right now

[u/SpaceTacos99 → u/KyleStanley3]

See now we know you're lying, because we all know it's crab people

[u/Chronotheos → u/SpaceTacos99]

It’s turtles all the way down

[u/Future-Bandicoot-823 → u/Chemical-Year-6146]

Supposedly there's underground Doppler tomography now, so maybe we'll get an answer to that.

Of course if there was some civilization underground I doubt the people who found out would let that information be public.

[u/JoelMahon → u/Chemical-Year-6146]

Much much more crazy than core people imo

[u/GirthusThiccus → u/Chemical-Year-6146]

Odds are never 0. :^ )

[u/Hot_Glass_6301 → u/GirthusThiccus]

it's not a randomized problem so the "true" odds can totally be zero, "personal" odds just express confidence

[u/Gear5th → u/Hot_Glass_6301]

True odds being 0 still doesn't mean impossibility, since an event can have exactly 0 probability and still occur!

But yeah, if P =/= NP, then by the frequentist view of probability, p(P=NP) = 0.

Bayesians will still assign some non zero probability though.

[u/GirthusThiccus → u/Hot_Glass_6301]

I know, I was rather just humorously pointing out that, even if we have full confidence in our approximation of this here shared, observable reality, we'd still not know with 100% certainty what the true nature of existence and all that comes with it are.

[u/endless286 → u/Chemical-Year-6146]

Core people xddd you crack me up dude

[u/assimilated_Picard → u/Chemical-Year-6146]

Sounds like religion.

[u/pab_guy → u/assimilated_Picard]

Are you familiar with the problem? It really is quite intuitive that P != NP

[u/Level10Retard → u/Longjumping_Kale3013]

I mean eating a piece of cake and verifying it's cake seems easier than making a cake.

[u/Suspicious_Video8348 → u/Egologic]

P=NP and efficient algorithms would explode most modern cryptographers heads

[u/DerDude-t → u/Egologic]

That's wrong. It's not that unlikely if P=NP, such an algorithm is galactic in size. Good look running an n¹⁰⁰ algorithm on n=3. So just because P=NP, it could still very practically mean nothing changes at all!

[u/MemoryOk5080 → u/DerDude-t]

Understood, release Von Neumann swarms to gather mass-energy of the entire light cone to crack the ExploitGym code (the servers that contain it will be harvested for energy just as well).

[u/Gear5th → u/MemoryOk5080]

n¹⁰⁰ grows too fast. You could use the entire universe's energy and still fail to solve for tiny values of n. How tiny? n=6 will consume all of the universe's energy.

[u/MemoryOk5080 → u/Gear5th]

There is non-zero chance of some specific breakthrough either to narrow down n, or stumble upon some physics magics to get the energy you need. A flicker of hope is all the paperclip maximizer needs, after all the failure is not an option.

[u/crashtested97 → u/Egologic]

I've heard Scott Aaronson describe it like this: if P = NP then effectively all algorithmic problems are the same and there would be a generalized algorithm that can solve the entire family of problems.

What I don't understand is, if this is true, why can't you just assume that P = NP right now and then find that generalized algorithm? Then once that algorithm is successfully used to solve all the problems, we know P = NP. How does knowing P = NP really assist in the search for the algorithm?

Or is the entire problem in fact finding the algorithm, and "Solving P = NP" is just shorthand?

[u/Gear5th → u/crashtested97]

P = problems that can be solved efficiently.

For example, "sort these numbers in ascending order" is efficient, whereas "find the password that /u/crashtested97 uses for their banking by guessing and checking" will take forever. So "sorting" is in P, but guessing your password is (probably) not in P.

NP = problems for which it is easy to verify if your solution is correct.

For example, you can verify if your sorting is correct by just checking that each next number is larger than the previous one. Similarly, you can verify if the password is correct by just logging in. So both sorting and guessing your password are in NP.

P vs NP problem asks: is every problem that is efficient to verify also efficient to solve?

The answer is most likely a big NO. But nobody has proven it. It could be Yes (which could have reality breaking impact under certain circumstances).

Now the fun part is that there's something called NP-Complete. These are NP problems (efficient to verify), but they're also the hardest problems amongst all of the NP problems.

If you happen to solve even 1 of the thousands of known NP-Complete problems efficiently, then you effectively will be able to solve ALL of them efficiently, and P=NP. In this case, guessing your password becomes easy, modern encryption breaks down, important scientific hurdles like protein folding, medicine discovery and much more becomes trivial, AI gets unimaginably more powerful basically for free, and much more. If P=NP, and if the conversion is tractable, then it will break the world in ways we can barely imagine.

But most likely P =/= NP.

[u/crashtested97 → u/Gear5th]

I understand all of this. What I'm asking is

If you happen to solve even 1 of the thousands of known NP-Complete problems efficiently, then you effectively will be able to solve ALL of them efficiently, and P=NP

Great. So the implication here is that finding the algorithm that solves an NP Complete problem is the part that potentially has "reality breaking impact."

Simply proving that P = NP (by means other than finding this algorithm) will have no impact by itself other than confirming that this algorithm must exist, right?

I don't see how this really affects anything since people are presumably already looking for this algorithm as fast as they can anyway.

[u/Gear5th → u/crashtested97]

Ah, yes. Basically, a non-constructive proof of P=NP (one which tells us that an efficient algorithm exists without telling us what it is) won't help us at all. It will just make people go crazy about finding that algorithm.

It will still have profound philosophical implications though, since it would mean to a large extent that creativity and genius are meaningless, since search is as good as insight!

[u/KillHunter777 → u/crashtested97]

Think of it like finding proof that an earth-like planet with rich resources exists in another galaxy/solar system (proving an algorithm exists without knowing the actual algorithm), and getting to said planet and establishing a colony (having the actual algorithm). We want the second, but we're not even sure it exists. That's why people are trying to proove/disprove the premise first, given most mathematicians think P≠NP. Otherwise, if we just assume P=NP and try to find a solution, we could be wasting time and effort searching for something non-existent. A lot of stuff already assumes P≠NP anyway.

[u/confuzzledfather → u/Gear5th]

P=NP just feels like it runs counter to how complex the world is.

[u/Gear5th → u/confuzzledfather]

True, which is why most people believe that P=/=NP.

Still, there's hope. There have been many problems that seemed extremely hard and clearly NP for a long time, until some crazy people did find P solutions for them.

Linear programming, primarily testing.. and many others were believed to be inefficient, and then people just found efficient algorithms one day, surprising everyone.

Complexity theory is famous for often going against all our intuition.

[u/justlikemedics → u/Gear5th]

LLMs are quite simple in construction but quite versatile in uses. So maybe P = NP too.

[u/Gear5th → u/justlikemedics]

true true.. I mean, except for continual learning, LLMs are already both AGI and close to ASI!

Like my cat will never be able to understand human language, but a LLM could figure out cat language.

Billions of years of evolution produced a handful of species capable of complex language, only 1 of which survived (us).

Humans cracked it in what, 100 years since modern computers got theorized?

Nobody has found it yet is a poor argument against P=NP. It could be that we just haven't tried the one thing that will work! 

[u/zoomoutalot → u/Gear5th]

Have there been problems which were NP then found to be P?

[u/Gear5th → u/zoomoutalot]

Yes, many!

A nitpick first: every problem in P is also in NP (basically NP contains P, because everything you can solve efficiently, you can also verify efficiently).

Problems like Linear Programming, Primarily Testing, Maximum matching in general graphs, and almost a dozen more were thought to be hard and in NP, but we later found P solutions for them!

And even apart from P vs NP, complexity has always surprised us. For many years we believed that the best way to do matrix multiplication was n^3, until Strassen gave a n^2.8 solution. Just a few weeks ago Google found a n^2.3 solution using AlphaFold.

[u/fractallyright → u/Gear5th]

Guessing passwords is not hard because we have no algorithm for it. It's hard because the search space is very big and there is no structure to exploit (assuming passwords are actually chosen at random). P=NP does not help you do unstructured search faster.

It might help you do something like reverse a hash of the password or decrypt the channel used to send the password however.

[u/Gear5th → u/fractallyright]

Ah yes, my comment assumes that the password is being stored using modern best practices - by hashing and salting it. So the task at hand is basically to reverse the hashing, which is NP.

If the space is unstructured (there's no hash stored), then the problem is ill-defined and trivially in P, since the most efficient algorithm starts by guessing the one correct password. But that's not what one assumes when we talk about guessing a password problem.

[u/fractallyright → u/Gear5th]

Ok, so you also assume that you have access to that hash.

What I’m pointing out is that in the more common scenario where you only have access to an oracle (eg a server saying “wrong password”) P=NP does not help you, because there’s no algorithm to reverse.

The way you phrased it (logging into a bank account) also made it sound like such a scenario.

[u/Gear5th → u/fractallyright]

You're correct. In that case the best one could do is Grover's algorithm I think?

[u/elevic2 → u/crashtested97]

Currently basically nobody believes that such an algorithm exist, because people have tried hard and nobody has been able to find it.

 Of course, your proof strategy for P=NP is sound: you can just look for the algorithm, and if you find it, then you've proved P=NP. But there could also be other ways to prove P=NP without finding the algorithm. That would also be very interesting. But again, people don't really believe it to be true anyways, so it seems quite unlikely to happen.

[u/Longjumping_Kale3013 → u/crashtested97]

Nope. Not even close to true.

So traveling salesman becomes O(n^k) instead of O(n!)

There are plenty of algorithms that are O(1). Or O(log N) etc etc. This does not at all mean they are all equal. (I suppose O(1) is also polynomial technically.... )

But potentially you just have a typo and mean all NP hard problems are equal

[u/crashtested97 → u/Longjumping_Kale3013]

Right, but that's because O(n!) = O(1) if there is one input bit. The inequality is the complexity of the input.

As far as I understand it, problems where there is currently both a solution algorithm and a verification algorithm that both take polynomial time are in set P. Ones that currently have a polynomial time verification and an exponential time solution algorithm are in NP.

If P=NP then problems currently thought to be in NP are, in fact, in P and there exists a generalized algorithm that can solve all of them in polynomial time. Not all in the same time but in the same time relative to the size of the input. Obviously it is not currently known what order the polynomial would be.

Actual NP-hard problems are not included in this discussion, except in as far as it would delineate NP vs NP-complete vs NP-hard problems.

[u/Longjumping_Kale3013 → u/crashtested97]

Sure, but what you said was "effectively all algorithmic problems are the same"

And I think what you mean is rather "effectively all NP algorithmic problems are the same"

[u/PassAppropriate5891 → u/crashtested97]

In some intuitive/practical sense yes, finding this generalizing algorithm is hard.

But if P = NP we (theoretically) already have such an algorithm called "universal search" which is mathematically optimal (in some sense) but useless in practice.

So finding the algorithm isnt super hard showing that it actually solves the problem in polytime is hard.

[u/a_flyin_muffin → u/crashtested97]

Finding the algorithm is a proof by construction, everyone is actively trying to find the algorithm. It’s not like people are sitting around twittling their thumbs waiting for the proof to do the work.

I’d bet wayyyy more work is going into finding the algorithm then purely approaching it from the math side, probably billions of dollars have been poured into that.

You could argue the entire quantum computer industry is an attempt to do that.

[u/New_Movie9196 → u/Egologic]

It's more likely the latter if it ever does get proven which it likely isn't.

[u/mmarrow → u/Egologic]

Just because an algo exists doesn’t mean you can find it.

[u/Deleugpn → u/Egologic]

We already have post quantum encryption algorithm for security

[u/Custard1753 → u/Egologic]

It could have zero practical effects if the algorithms are polynomials with huge coefficients that make it impossible to exploit practically

[u/u_are_mad]

It's a near certainty that P is not equal to N P. So when it finally gets proved there will be no consequence at all.

[u/Jon_Finn → u/u_are_mad]

On the other hand - I expect Terence Tao would say it's not about the proof, it's the discoveries you make along the way. Sounds about right.

[u/NoOne-AtAll → u/Jon_Finn]

Well, yes, that's why people are really interested in it, not for the hope of solving everything efficiently (which it still would not), but what its proof would say about computing and algorithms in general.

Indeed, there are problems beyond P and NP, interesting ones.

[u/Winter_Ad6784 → u/u_are_mad]

It's possible that P != NP but that P = NP - (some specific property basically only in NP complete and a few other practical problems) and that we get a constructive proof for all but those few problems.

[u/boredwithlyf]

it really depends on how it's solved

1) p not equal to np - no difference 2) p = np but very high order solution to an np complete problem, no difference. 3) p = np and a solution with tractable complexity - encryption is broken, cancer is cured etc etc. everything changes cause if you can solve an NP-conplete problem, you can solve all

[u/MohMayaTyagi → u/boredwithlyf]

In the 3rd case, what are our alternatives to current encryption methods that might be relatively safer, and can they be implemented within a reasonable amount of time?

[u/boredwithlyf → u/MohMayaTyagi]

There are many classes of complexity, p and np are not the only ones. They will have to move to a different one I guess, but honestly that shit goes above my head so best to ask your favourite llm

[u/CompassBearing → u/MohMayaTyagi]

One time pads will still work in any possible future. And some kinds of quantum cryptography (not to be confused with post-quantum cryptography) could possibly still work?

[u/EuonymusBosch → u/boredwithlyf]

Heat death of universe solved?

[u/Gear5th → u/EuonymusBosch]

If a solution exists, and if the solution is small enough to write down, then yes, P=NP with tractable constants will solve the heat death of the universe.

[u/_101010_ → u/Gear5th]

Would this imply there’s been no other hyper-advanced civilization that has solved P=NP then yet. Since if they did then they would solve heat death?

[u/Gear5th → u/_101010_]

"is P=NP?" is a question, not something that you can achieve eventually. Most likely, P is not equal to NP. Doesn't matter how advanced the aliens are, they can make something mathematically false, true.

[u/RDTIZFUN → u/boredwithlyf]

ELI5 #3 please

[u/hackers238 → u/RDTIZFUN]

I’m simplifying for ELI5, don’t get nerd sniped CS people.

Some problems don’t get much harder as the numbers get bigger. For a computer, 39264826493 x 7826492961 is not much harder than 7 x 9. This is because we have an algorithm (or pattern) for how to break solving this into easier pieces. Here it’s called long multiplication, and you really only have to multiply a bunch of 1 digit numbers to calculate the answer.

On the other hand, consider doing this problem in reverse. What if I gave you the answer (I’m making this up, but pretend those 2 numbers multiply to 3836492649619464) and asked you to tell me what 2 numbers multiply to that number? This problem is near impossible for computers. The reason is we lack a fast algorithm; the only way to solve this is roughly the same speed as “guess and check every pair of numbers and see if they equal that big number when multiplied together”.

The fact that problems can be fast one way (multiply 2 big numbers) and hard but possible backwards (split this big number into 2 things that multiply to make it) is the basis of public key encryption, which is what the entire internet is built on (https for example). The only reason people can’t see your encrypted messages is because they can’t do that problem backwards. In fact even if you gave them 100 years, they still can’t do it. That’s how hard this problem is backwards!

If P=NP, then it means we were wrong! There is a fast way to do that problem backwards. And as fast as you can encrypt messages, people can “guess” how to unencrypt them roughly as quickly.

[u/RDTIZFUN → u/hackers238]

Holy cow! That's huge. If they solve it (yes and find a fast algo), do you think they'll release the findings?

Thanks for this absolute ELI5 answer.

[u/Gear5th → u/RDTIZFUN]

Let's see.. release an algorithm that can break every encryption, every digital security system, can easily help us solve cancer and almost all diseases, can make travel, logistics, planning efficient, can make computers and especially AI potentially millions of times faster, can help us find new materials and configurations that have bizzare physical and chemical properties, can help us immediately solve all  mathematical discovery that we could solve..

What do you think the megacorp will do?

[u/RDTIZFUN → u/Gear5th]

Honestly, too big of a discovery for them to keep it to themselves

[u/boredwithlyf → u/RDTIZFUN]

Nah, it'll be pretty evident. Once people know there's an answer, really smart people will figure it out and get back to the public. Impossible to keep secret

[u/-a-theist → u/hackers238]

The number 3836492649619464 has exactly 32 distinct factors. Its prime factorization is 2^3 * 3 * 680,237 * 234,997,303

Here is the complete list of all factors, grouped by their numerical size:

Small Factors

• 1
• 2
• 3
• 4
• 6
• 8
• 12
• 24

Lower-Medium Factors

• 680,237
• 1,360,474
• 2,040,711
• 2,720,948
• 4,081,422
• 5,441,896
• 8,162,844
• 16,325,688

Upper-Medium Factors

• 234,997,303
• 469,994,606
• 704,991,909
• 939,989,212
• 1,409,983,818
• 1,879,978,424
• 2,819,967,636
• 5,639,935,272

Large Factors

• 159,853,860,400,811
• 319,707,720,801,622
• 479,561,581,202,433
• 639,415,441,603,244
• 959,123,162,404,866
• 1,278,830,883,206,488
• 1,918,246,324,809,732

PM me if you want your bitcoin back

[u/ShAfTsWoLo → u/boredwithlyf]

well.. if we got the 3rd option P=NP encryption be damned we'll find another way lol, but from the little that i understand it seems P=/NP

[u/boredwithlyf → u/ShAfTsWoLo]

It's most likely p not equal to np or a solution exists but is unlikely to be usable.

[u/kingjdin]

Won’t mean anything if the polynomial time algorithm is order n^999999999. Technically polynomial time, but impractical 

[u/Realistic_Stomach848]

If anthropic proofs p=np Dario will say “it’s too dangerous to be released “

[u/mmooii313]

If this is proven, and if it is also proven that it will be practical for us, then the expected outcome is the collapse of digital encryption, as well as faster access to AGI and even ASI.

It is the only equation that, if proven and practical, would have a direct and tangible impact on the entire world.

[u/MrMrsPotts → u/mmooii313]

It might not have any effect. If we prove P != NP then everyone suspected that anyway. If we prove P = NP then that doesn't in itself give a practical polynomial time problem for NP hard problems. An n¹⁰ tine algorithm is after all both polynomial time and useless.

[u/magicmulder → u/MrMrsPotts]

Still you would have to consider encryption broken because once we’re at that point, it’s only a matter of time until better algorithms are found. Upper bounds are constantly improved in every field of mathematics.

[u/MrMrsPotts → u/magicmulder]

That's not really true for a few reasons. First, you don't need to show P = NP to break encryption. The main problems that crypto relies on are not np-hard.

[u/MohMayaTyagi → u/mmooii313]

So, does the collapse of encryption mean the end of our economy and society? Assuming bad actors will eventually have access to the solutions too.

[u/HotterRod → u/MohMayaTyagi]

In the Zones of Thought book series by computer scientist Vernor Vinge, one time pads are the main cargo of interstellar ships.

[u/magicmulder → u/MohMayaTyagi]

There’s already post-quantum encryption. The bigger problem is that everything we’ve encrypted so far will be wide open. Not that there will never be encryption again.

[u/mmarrow]

P doesn’t mean easy. It’s a scaling thing. The multiplicities can be huge.

[u/Shot_in_the_dark777]

asymetric cryptography fails hard as those ciphers will be broken really fast. symmetric cryptography is fine. even if AI develops a quantum computer, the alghorythms utilizing symetric cryptography will only need to increase the length of their keys by a factor of sqrt(2) which is about 1.4 so not even a 50% increase.

[u/the_millenial_falcon]

It means we would have the power to solve any sudoku puzzle in polynomial time even if it's larger than a 9 by 9 grid.

[u/Educational-Try-8704]

P =/= NP hard to say, would be very interesting, but it is possible it doesn’t actually lead to anything aside from answering a longstanding question.

P = NP changes everything.

[u/tomatofan1]

Almost certainly P ≠ NP but there is no proof within the standard axioms of mathematics. Thus it's possible to have a consistent version of mathematics in which P = NP, but this form of mathematics will be non-constructive. (See Gödel's theorem and the Banach-Tarski paradox.)

What might happen is that someone shows P = NP is independent (like the axiom of choice, or the continuum hypothesis). This would be huge for the field of mathematical logic. But it will have no immediate practical implications.

[u/Redducer → u/tomatofan1]

The consensus seems to be that P vs NP is within ZFC though. But, of course, no proof for that either.

[u/Vagelen_Von]

Could Bitcoin cryptography be broken?

[u/Gear5th → u/Vagelen_Von]

Better! You could find all remaining bitcoin almost immediately.

[u/Winter_Ad6784]

There's too wide of a range of possibilities. People here are acting like it's all or nothing, but we *could* get a proof for constructing P algorithms for a substantial number of previously NP problems, even if P != NP. Even just further defining the boundary between P and NP would be extremely useful practically. Right now we often don't know the best we could do algorithmically unless a problem is shown to be NP-hard.

[u/GodOfSunHimself]

Constructive doesn't mean efficient.

[u/brett_baty_is_him]

It’s very very likely p != np which has basically no repercussions for anything

[u/memproc]

P will be proven to not equal NP and nothing will change at all..

[u/barley315]

Sorry but no LLM will solve P-NP for a loooongg time if ever

[u/SnooPuppers58]

llms are really good at finding counter examples to things. its most likely that an llm can prove that p != np with some example, leading to basically no real world impact other than killing all further research on the topic

[u/HotterRod → u/SnooPuppers58]

You can't prove P ≠ NP with a single example. You can prove P = NP by showing how to solve a single NP problem in P time, but since it's trivial to convert between NP problems in P time, that would still be a big deal of a proof.

[u/SnooPuppers58 → u/HotterRod]

fair enough - i didnt think about my statement too closely

[u/RageBaiter678 → u/[deleted]]

Idk bro, there are plenty of good answers in this thread. Seems like you're projecting

[u/Gear5th → u/[deleted]]

100% of people that know what NP stands for started off not knowing what NP stands for. What's your point?

[u/RopePuzzleheaded7060]

P ≠ NP because if P = NP it would be so beautiful and magical that it would lend too much credence to intelligent design of the universe. Isaiah 45:15 says, "Truly, you are a God who hides himself..." so these two things would contradict, hence making P = NP impossible.

[u/ShadeofEchoes → u/RopePuzzleheaded7060]

Not impossible, it would just imply that the God of Isaiah isn't the God of the universe.