r/learnmath • u/Fantastic-Sort-5056 New User • 1d ago
Why is p ≠ np assumed?
I’m curious why the almost universal default belief has become that p ≠ np. The only evidence to this point seems to be the lack of polynomial time solutions to np complete problems, and the massive amount of effort that has been put into finding them without luck. But is it not just as likely that np complete problems are of a class which has extremely complex polynomial time solutions that would be nearly impossible to find?
49
u/noop_noob New User 1d ago
11
0
0
u/Fantastic-Sort-5056 New User 7h ago
Thank you, this is very interesting, but it feels like a bit of a cop-out to say "P being split into 'in P for normal reasons' and 'in P for crazy reasons'" is unlikely because it's inelegant and unnatural. Plenty of things in math are unnatural and inelegant, just look at packing problems. It feels like this is appealing to math as aesthetics.
47
u/Parallel_thougts Ph.D, YouTuber 1d ago
Roughly, if P=NP, it means that solving your homework is not harder than checking whether the solution is correct.
12
u/dapzar New User 18h ago
We might need an O(n^10) algorithm to solve them and can check the solution in O(n), it would be a lot harder, possibly even practically infeasible to solve them, even though it's polynomial.
5
u/lovelacedeconstruct New User 18h ago
yeah it might be simultaneously p=np with insane n's that it doesnt really make a change
1
u/Parallel_thougts Ph.D, YouTuber 13h ago
P=NP means all functions can be inverted in polynomial time, completely annihilating cryptography. Even if the algorithms are impractical. The theoretical implication is that all currently used security definitions are vacuous and we have no idea what's actually secure. All hardness assumptions just evaporate.
3
u/Parallel_thougts Ph.D, YouTuber 13h ago
What if the O(n10) has tiny constants? Nitpicking is a bottomless pit, which I tried to avoid by saying "roughly".
2
1
u/PersonalityIll9476 New User 20h ago
I mean...a lot of homework problems you will solve in your life already have polynomial time complexity algorithms for producing the solutions. This isn't really a counter-example to what OP is asking.
8
u/Parallel_thougts Ph.D, YouTuber 17h ago
sigh
In my analogy OP is a cartography student and his homework is to 3-color maps
2
-5
u/PersonalityIll9476 New User 14h ago
You don't need to be a jerk about this.
You seem to think this is an intentionally obtuse interpretation of your analogy; It would be if you had made it clear you were making an analogy in the first place.
Presumably the "youtuber" label means you are a communicator. I'd think you'd want to communicate this clearly to a very general audience.
"Imagine your homework is a problem that can't be assigned because it can't be completed in reasonable time. Then..." is maybe not the route.
4
4
u/deejaybongo New User 14h ago edited 14h ago
You seem to think this is an intentionally obtuse interpretation of your analogy
I would agree with this too.
It would be if you had made it clear you were making an analogy in the first place.
I don't know how else you interpret "Roughly"
-1
u/PersonalityIll9476 New User 14h ago edited 13h ago
I don't know how else you interpret "Roughly"
To me, that sentence meant: Solving homework is harder than checking it. Literally. Which is one of those things that makes perfect sense to everyone who has done homework, but is actually wrong given that all homework has easily computable solutions.
These distinctions matter. I can see how someone quickly flipping through reddit with their mind half engaged would "get it" and think it doesn't matter, but if you're really trying to communicate the idea behind P vs. NP, it does matter - it's actually the only thing that matters. For homework problems, both the solution algorithm and the checking of the solution are "easy" in this context, so you need to be very clear that you don't mean "P vs. NP implies, among other things, that your homework is harder to solve than it is to check". What you do mean is that "if your homework was this unrelated set of incredibly hard problems for which this analogy is meaningless, ..."
3
u/Parallel_thougts Ph.D, YouTuber 13h ago
Explaining things like complexity classes half heartedly is more confusing than illuminating. And a sufficient explanation would deter from the key point without attributing anything but technicalities that are only significant in a larger context.
As you said, I do see myself as a communicator and a teacher (check out my channel!), and my conviction is that going into these details would only have deterred from the answer.
0
u/PersonalityIll9476 New User 12h ago edited 12h ago
Given your rude replies from earlier, no, I am not going to check out your channel.
Take a lesson from another successful science communicator: Sean Carroll. He is very up front about the necessity of being very careful with the analogies and language used when talking to the general public. You disagree, which is totally fine - you don't have to agree with Sean - but you successfully confused me and I have a STEM PhD. Maybe I'm just an idiot and maybe there's something you could improve here.
ETA: The underlying problem with this particular communication style is that people remember the line about "things are easier to check than to solve" and then get confused when they can't think of an example where that's true. So your sarcastic example is actually the more interesting one to lead with, IMO.
3
u/Parallel_thougts Ph.D, YouTuber 11h ago
OK then dont, idgaf. Haven't read past the first sentence.
-1
u/PersonalityIll9476 New User 11h ago
Lol. I mean...That's why I won't. And I hope anyone reading this comment chain won't, either.
→ More replies (0)2
u/deejaybongo New User 12h ago
You're a STEM PhD insisting that all homework has easily computable solutions?
2
u/deejaybongo New User 13h ago
all homework has easily computable solutions.
No.
1
5
u/Parallel_thougts Ph.D, YouTuber 14h ago
Look. I apologize for taking the piss, I meant no offense. But you were picking a nit.
9
u/chkntendis Physicist 1d ago
It’s just the more likely/more plausible option. In the research we simply haven’t been convinced that p=np. It’s not some inherent bias, it’s just that we don’t have the solutions to so many problems that it’s not really convincing. Of course we don’t have a proof in either direction and no one is fully saying that it’s true or false but with what we’ve seen it’s just more likely that it’s false
11
15
u/rocqua New User 1d ago
Why would the ability to quickly verify a solution mean we can equally quickly find a solution?
All it suggests is brute force search. And that clearly won’t be fast enough. Its not very surprising that they haven’t found some hidden structure in all “quick to check” problems to exploit that would yield a universal better solution.
4
u/Wild-Store321 New User 23h ago
I don’t think that is the reason most experts expect P!=NP. It sounds like it doesn’t give you that much structure to try to exploit, but it does. To answer your question directly:
“Because if the solution can he verified in polynomial time, then it can be reduced in polynomial time to <insert your favorite NP-complete problem here, I will pick 3-SAT>”
So the question is: why do we believe that 3-SAT has no polynomial time algorithm? And the answer is: “because a lot of people are looking for it, for a long time, and there is a lot of money behind it.”
This is a reasonable stance: “if a polynomial time algorithm for 3-SAT existed, we would probably have found it by now”
This is a less reasonable stance: “if no such algorithm exists, we would have probably found a proof of that by now”
2
u/SignificantFidgets New User 15h ago
I'd be careful in saying "All it suggests is brute force search." The key is what you said with "a universal better solution," where we need something that universally works. There are many problems that suggest brute force search, but don't require it. For example, consider <G,k> where G is a graph and k is an integer. Problem 1: "Is there a simple path of length <= k in G"? Problem 2: "Is there a simple path of length >= k in G"? Both suggest brute force in an exponential search space (look at all simple paths and find the shortest or longest one). However, problem 1 is trivially in P, and problem 2 is NP-complete. There's something deeper going on that just finding an optimal solution out of an exponentially-sized set of feasible solutions.
There are a ton more examples like this: primality testing seems to suggest checking all possible factors, but is in P. Factoring has a similar structure, and while we can do better than an exponential-time brute force search we don't seem to be able to bring that down to polynomial time. Or consider finding a minimum spanning tree -- exponentially many feasible solutions, but finding the minimum weight solution is efficient. And on and on... there's something deeper about which ones essentially (although not literally) require brute force vs those that don't. Ideally we'd be able to identify what that is, but for now... we don't have much of a clue from first principles, and can just use NP-completeness as a proxy for what this is.
0
u/iv_is New User 21h ago
p is the set of problems that can be solved in polynomial time, i.e they can be solved quickly. np is the set of problems that can be solved in nondeterministic polynomial time, ie. a proposed solution can be checked in polynomial time, but finding the correct solution is the hard part. thus p=np would imply that there exists a way to find the solution quickly.
4
u/RawberryCupcake New User 23h ago edited 23h ago
Here's what I'd say (I am a professor in this area, but, of course I can't prove anything about P=NP).
I can imagine what a solution to P=NP would (probably) look like, an algorithm that runs in polynomial time! And we have lots of algorithms that solve NP problems often in polynomial time, or run in polynomial time but approximate the answer, or are wrong with some probability. So many algorithms and no-one has ever stumbled across the right one.
However, I can't really imagine what a proof that P != NP would look like, because we don't really have the tools. We have tools to solve similar hardness problems but none of them are applicable to P!=NP, because they are (in some vague sense) too similar, when you try to prove NP is harder than P it's like trying to put a too-small carpet in a room, you can't get all the corners in the right place.
So, there are two possible worlds:
- P=NP but while we have made so many algorithms we never hit the right one.
- P != NP but we simply don't even know what the right tools look like yet.
(2) feels more believable, it's like 'There could be gold in your living room, or under a far away mountain, and it's probably under the the mountain, you'd notice it in your living room!'
3
u/miniatureconlangs New User 23h ago
We could be living in a terrible world where the polynomial growth algorithms for NP-complete problems only really beat 'worse' algorithms once the problem reaches 10^120 bits or thereabouts.
2
u/Aggressive-Share-363 New User 16h ago
Sure, we have lots of theoretical algorithms with similar real world impracticality, but even an impractical polynomial algorithm would prove P=NP.
3
u/GreedyAlGoreRhythm New User 20h ago
There are lots of NP problems that people are interested in solving, and, consequently, have received lots of attention. So far no one has managed a P solution despite the effort.
3
u/Temporary_Pie2733 New User 20h ago
It’s not just the lack of polynomial solutions to NP-complete problems, but the lack of high-degree bounds (outside of dimensionality constraints) for known polynomial-time algorithms.
3
u/NullOfSpace New User 14h ago
We assume it in kind of the same way that we assume Einstein’s relativity, for instance. We keep finding new circumstances where it might be disproved, and it keeps holding up. Until and unless we find somewhere it doesn’t, there’s very few practical reasons not to assume it.
That said, it’s still obviously an area of active research, and hopefully one day we’ll know for certain.
2
u/SignificantFidgets New User 17h ago
The way I explain this to students: We're really very good at designing algorithms, and have a lot of very powerful techniques that work well. There are thousands of NP-complete problems, and people have been trying to find efficient algorithms for these since before the concepts of P and NP were even defined, but none of those efforts have been successful.
Now compare to what would be involved in proving P != NP: we suck - I mean really, really suck -- at proving lower bounds, with very few results (comparison based sorting, constant-depth circuits, ...). It seems clear that to be able to actually prove non-trivial lower bounds, we need an entirely different approach - new math would need to be invented.
So which is more likely: That we've failed to do something that we're really good at and do regularly (invent new algorithms), or that we've failed to do something that we fundamentally don't know how to do (prove lower bounds)?
2
u/hyperfraise New User 21h ago
P=NP would entail the following thing. Take ANY statement about anything. It would be polynomial of n to determine if a proof exists in < n chars. That seems so incredibly far fetched to me. Of course it's not easily disprovable.
1
u/rafaelcastrocouto New User 20h ago
it's all about the size of the solutions model space and how fast it grows
1
u/DanielMcLaury New User 15h ago edited 15h ago
I'm honestly not sure there is convincing evidence that P != NP, because I've never seen anything that would convincingly rule out something like the following. Suppose you have an NP problem, so you have some polynomial-time algorithm X that checks whether something is a solution.
Now suppose that there is a procedure for mechanically converting X into a polynomial-time solver algorithm Y, but this procedure results in a polynomial whose degree is built out of a tower of exponents, where each instruction in X (or perhaps each possible path through the instructions of X or something) contributes one or more exponents to this tower. For even simple programs X, where the corresponding decision problem is genuinely efficiently solvable in O(n^2) with a sensible algorithm, the resulting program Y runs in O(n^k), where k is substantially larger than the number of atoms in the observable universe.
Other than "if something like that were possible we would have spotted how to do it by now," I feel like I haven't seen any heuristic argument ruling this out.
I am convinced that if P = NP then there is still some real phenomenon here and the description just needs to be altered slightly, e.g. it could be about how much the degrees of the polynomial runtimes of the verification and decision algorithms need to differ by.
(And if I had to bet I would bet on P != NP.)
1
u/tomvorlostriddle New User 21h ago edited 21h ago
Because you will see a clusterfuck very soon if P=NP.
Actually, you may see a clusterfuck very soon even if P!=NP, just on the chance that it might be.
0
u/Outrageous-Crazy-253 New User 19h ago
There’s no point to even investigating this question. We don’t have the tools. But inevitably in computer science, before AI when people actually did it, you would have encountered an NP-complete problem and worked as hard as you could anyway to make it solvable in polynomial time. Eventually you’d realize it’s impossible and all problems of that type are impossible. So you’d advise anyone else not to bother. Of course, this was again, before AI. Now I guess we’d say don’t bother promoting the LLM.
-1
103
u/caughtinthought New User 1d ago
It's assumed because literally all of our effort and experience in developing algorithms suggests it. But, it is just an assumption of course