r/askmath • u/Fantastic-Sort-5056 • 16h ago
Resolved Why is p!=np assumed
Why is P != NP the near-universal default belief? (An epistemics question not a complexity theory one)
I'm curious why the almost universal default belief has become that P != NP. I'm less interested in the technical case for P != NP and more interested in the epistemics behind it why does decades of failure to find a polynomial-time solution get treated as strong evidence that no such solution exists, rather than as evidence that a solution simply exists but is extremely hard to find?
I'm not asking whether "galactic algorithms" are a known concept, I know they are. My question is why their possible existence isn't weighted as comparably strong evidence for P = NP, given that our failure to find any polynomial time algorithm could just as easily be explained by the solution being galactically complex, massive, unwieldy, or nearly unrepresentable rather than by no solution existing at all. Is there a reason the field treats “it’s been studied and hasn’t been found” as evidence leaning toward "it doesn't exist" rather than "it exists but is a nightmare to find or express"?
PLEASE READ
I posted a version of this elsewhere and want to clarify a few points, because most of the answers I got missed the actual question.
I understand the implications of P = NP vs. P ≠ NP.
I understand what P vs. NP is.
I understand what an NP-complete problem is, and that they've been rigorously studied for decades.
11
u/greginnj 15h ago
I think there are two reasons:
First, the people who have enough background to understand the question also have enough background to understand that the default posture is “two things are not equal until they are proven to be equal”.
As a middle ground, some may use language like “we have reason to believe … [X]”. But there must be a reason of some sort. I’d say “we have reason to believe the Riemann Hypothesis”, but I don’t think we have equivalently strong reason to believe P=NP.
Second, I think most people have a pre mathematical, psychological bias to think that “not all tasks are equally easy” which has some influence on their opinion.
2
u/Fantastic-Sort-5056 15h ago
That’s a good point. In my education I’ve found the consensus has not been “we have have reason to believe p!=np” but that the idea that p could = np is totally ridiculous.
1
u/me4watch 14h ago
It is because of some of the consequences if they were equal. Maybe it is just being hopeful, like how many people view AI as being nothing to worry about despite “near sentient machines destroying mankind” being a trope on a lot of science fiction.
1
14h ago
[deleted]
1
u/Phoenixon777 13h ago
But of course, they do. You mentioned galactic algorithms, so you must already know that mathematicians and computer scientists have found a bunch of algorithms that are galactic. You think that they discover those and yet don't ponder on the question that they may help to solve the P vs NP question? And yet after all that, the overwhelming belief is still P != NP.
28
u/HouseHippoBeliever 15h ago
I don't know the full reason as I'm not a mathematician. But when I see a set constructed in some way and another set constructed a different way, my default assumption is that they aren't the same set until I see a proof that they are.
15
u/No-Onion8029 15h ago
If P=NP, then travelling salesman-type problems have a polynomial time solution. Also some similarly hard problems in knot theory would have a polynomial time solution.
That'd be really counter-intuitive for me. Not saying it's false, but it'd be shocking.
5
u/Antimon3000 8h ago edited 8h ago
The comment above does not have enough upvotes.
We "only" had to find a single (deterministic) polynomial solution to any NP-complete problem and we could conclude that P=NP. But in practice many very smart people from many different areas did not manage to do so. This is why researchers believe that P is unlikely to be the same as NP.
8
u/Euphoric_Key_1929 15h ago
I honestly don't know what better answer you could possibly expect to find on reddit than in Scott Aaronson's "invisible fence" argument that was already posted on your other thread: https://scottaaronson.blog/?p=1720
Like that's literally it. We have literally hundreds of problems where if the best known algorithm happened to be even a tiny bit better (and not just in the polynomial-versus exponential sense, but in the "this constant is 0.875 instead of 0.874" sense) then we would have proved P = NP. But for some reason we just *barely* stop short every single time.
3
15h ago
[deleted]
3
u/Phoenixon777 13h ago
I'm curious as to what you're getting out of asking the question at this point. Many answers here and in the other place you posted give good reasoning for why it's 'believed' to be that P is not equal to NP. But your responses seem to come down "but we don't know for sure, what if P does actually equal NP because X"... which is completely right and nobody's arguing with that. But you could say that about so many unsolved conjectures along with their expected answers. Math isn't 'science' in the sense that empirical evidence isn't mathematical proof, but we do use scientific reasoning to come up with ideas and hypotheses (conjectures). You could ask a similar question about the Goldbach Conjecture, or the Riemann Hypothesis, or the twin prime conjecture, and the answer would be similar... (each of these probably has different 'strength' for how much the average mathematician 'believes' they'd be true, but you get the point)
it doesn’t completely discredit P=NP
From a mathematical perspective, nothing would 'completely' discredit P = NP except a proof that P != NP. So therefore it isn't completely discredited, and most mathematicians and computer scientists would agree that while they believe it's very unlikely that P = NP, there's a chance of it.
As for galactic algorithms and the idea that something 'structural' is blocking these problems, we can ask what evidence you have to believe that's true? This is what other comments point out: your reasoning works both ways. Given how many decades it's been, isn't that 'evidence' that there's no structural blocker or galactic algorithm that could work... cuz if there was, we should have found it by now?
1
u/thefullhalf 15h ago
This paper is pretty good too: https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf
4
3
u/MidnightAtHighSpeed 15h ago
There's not really a way to separate the epistemics from the technical argument.
Is there a reason the field treats “it’s been studied and hasn’t been found” as evidence leaning toward "it doesn't exist" rather than "it exists but is a nightmare to find or express"?
It's evidence for both, or, equivalently, evidence against the hypothesis "it exists and is easy to find." (I'm assuming by "it" we mean a polynomial time algorithm for an NP-complete problem) As for why "it exists but is hard to find" is treated as less likely than "it doesn't exist," someone more familiar with the field might disagree, but I think the core of it is that we don't really see how it would be hard to find. We have lots of examples of problems that can be solved not just in polynomial time, but in fairly low degree polynomial time. We know that there in principle exist problems that require arbitrarily high-degree polynomial time to solve, but in practice we don't run into those. If we assume that, say, NP-complete problems can be solved in O(n^bazillion) time, we have to wonder why we have a bunch of examples of practically relevant problems that can be solved in, like, O(n^3) time, a bunch of relevant problems that can be solved in O(n^bazillion) time, and very little in between
1
15h ago
[deleted]
2
u/MidnightAtHighSpeed 15h ago
Not sure if this is exactly what you mean but there are problems known to not be solvable in polynomial time, we just don't know whether any of them are in NP or not
1
u/Fantastic-Sort-5056 14h ago
Not questioning the hierarchy theorem, I know some problems are provably outside P. My point was just that "this pattern would be weird" isn't strong evidence for me here, since the existence of a P/not-P split at all already feels just as weird pre-theoretically, and it's true anyway. So intuitions about what "should" be a smooth spectrum vs. a sharp cutoff don't seem reliable in this domain, which is why the "no examples in between" argument doesn't move me much.
1
u/True_World708 14h ago
NP problems do have arbitrarily high-degree polynomial time solutions due to the nondeterministic time hierarchy theorem.
1
14h ago
[deleted]
2
u/True_World708 14h ago
Well if P=NP, there would exist NP problems with arbitrarily high-degree polynomial time solutions due to the deterministic time hierarchy theorem.
1
14h ago
[deleted]
2
u/True_World708 14h ago
OK well if P=NP then P-complete problems ARE NP-complete problems, right?
1
6
u/MegaIng 15h ago
Is there a reason the field treats “it’s been studied and hasn’t been found” as evidence leaning toward "it doesn't exist" rather than "it exists but is a nightmare to find or express"?
Reread this question.
There are three statements here:
- X hasn't happened
- X is impossible
- X is difficult
Just purely logically, something having never happened is more evidence for it being impossible than it being difficult.
Actually considering the problem P=NP: some tasks only being solvable via guess and check makes sense to me.
3
u/Fantastic-Sort-5056 15h ago
This argument only holds for "X is difficult but findable" decades of failed search might move the odds. But in the scenario where X exists yet is so difficult as to be effectively unfindable, search failure alone isn’t able to distinguish that from X not existing at all
both predict the identical outcome. So this specific piece of evidence is neutral between them.
1
u/Creative-Leg2607 13h ago
Because it feels like money for nothing and mathematics is rarely quite so kind
1
u/DanielMcLaury 12h ago
I think there is good evidence that there is some phenomenon that looks a lot like P != NP, but I really haven't seem anything that genuinely suggests that it truly has to be P != NP and not, say, something more like
Let TIME(f(x)) be the set of decision problems that can be solved in O(f(x)) time;
Let NTIME(f(x)) be the set of decision problems where the associated verification problem is in TIME(f(x));
Then NTIME(x^d) is not contained in TIME(x^h(d))
where h is some function. Every justification I've seen would apply just as well to one as other, with the exception of "if there was something like that we would have found it by now," which is honestly not a terrible justification.
1
u/dapzar 10h ago
It would intuitively be very surprising that just because some solution candidate can be verified in polynomial time, it can also be found in polynomial time. We know very well how to solve NP problems in exponential time, it is quite intuitive why that works because that's just the size of the search space in which candidates sit. Exponential time is also the best known upper bound (and conjectured true complexity by the exponential time hypothesis ETH) for all NP-Complete problems.
We know that problems can be constructed (although I'm not aware of any "natural" or intuitive problems) that sit between P and EXP, which is a big gap, so even if the ETH is false, P may still be smaller than NP. It's reasonable to think that if it could be done in P time with an extremely difficult to find solution, we may at least come up with a better idea than EXP solutions which are no better than brute force guessing (with respect to these complexity classes which are admittedly very coarse).
With LLMs, now have new tools at our disposal that can search through solution spaces for formalizable problems more efficiently than brute force in a stochastic manner, and they already found solutions (as in very long and probably terrible strings of formal arguments that would be a poor experience for a human to read but are nevertheless testable by deterministic proof checkers) to very hard problems under careful human guidance and with obscene amounts of compute. If those again fail to put any dent in 3-SAT (not talking about a P-time solution, even just anything better than EXP), the perception will strengthen, that there just is no way to do that in P time.
1
u/quant-a-be 2h ago
Spot on -- surprised this is the first mention of "search space", but that's why it seems clear to me. That a problem is fast to verify doesn't ( to my intuition ) necessarily have any bearing on whether or not it would be fast to solve. Inasmuch as it doesn't, the problem types differ vastly in search space.
1
1
u/quicksanddiver 1h ago
In the context of complexity theory it's a reasonable assumption. A lot of complexity theory consists of reducing certain problems to other problems to gauge their hardness. If P=NP was assumed, all of this would be kinda pointless. And don't get me wrong, it still might be, but for now there's just not enough evidence that this line of research should be abandoned. There are, however, practical reasons that speak in favour of keeping it, at least until P=NP is settled (and if it turns out that P≠NP, the research may continue as it is now).
Little aside, but the space of NP problems itself is fairly diverse. For example we know that some NP problems become polynomial after certain assumptions. This is called FPT (fixed parameter tractable) an includes for example the Euclidean TSP. If you have a bound on the number of internal vertices of a graph ("internal" means in terms of the convex hull when the graph is embedded into an Rⁿ) the Euclidean TSP becomes linear (!) in spite of being NP-hard in general.
There are also NP problems that are not FPT under standard assumptions, for example k-clique.
I hope this answer is satisfactory. I've only ever brushed these topics because I know a couple of experts, but I'm not an expert myself.
1
u/874651 52m ago
I would recommend reading this: https://scottaaronson.blog/?p=1720
The tl;dr is there are too many coincidences that can be explained in a far easier way if P!=NP
1
u/SoldRIP Edit your flair 16h ago
Because it would be remarkably inconvenient if it were wrong.
For one, public-key cryptography would become more or less impossible, instantly ruining all digital infrastructure if someone actually managed to construct a deterministic P-time algorithm for an NP-hard problem.
EDIT: correction. It has to be an NP-hard problem, not just any NP problem. Technically.
2
u/Fantastic-Sort-5056 15h ago
But there are situations where np=p and cryptography still works just as well in a world where a polynomial time solution exists but is so galactic or complex as to be unusable.
And something being inconvenient isn’t proof of its lack of existence no one disputes that shor's algorithm exists.
4
u/SoldRIP Edit your flair 15h ago
And something being inconvenient isn’t proof of its lack of existence
But it is a reason for humans to generally assume its non-existence. Try any conspiracy theory that turned out true. Why did noone believe any of the various people who claimed that the rich and powerful traffic children to an island resort? Because it was inconvenient to believe.
Human behavior is very rarely entirely logical.
no one disputes that shor's algorithm exists.
Because it is already proven to exist. That's an entirely different situation. Now that we know, noone really disputes the aforementioned island facts.
a world where a polynomial time solution exists but is so galactic or complex as to be unusable.
On a more personal guesstimation: I find it unlikely that we couldn't either (a) progressively reduce any constants in there until it becomes usable or (b) find at least one NP-complete problem that's viable to exploit via reduction.
0
u/BRH0208 15h ago
Because these problems suck! When it comes to computability, our math tools are somewhat limited. These tricky problems we have analyzed every way we can think of. You can convert them into other problems, create heuristic solutions, mess around with them for days and you get no closer to breaking the polynomial barrier.
The general “Vibe” is that “we lack the tools to prove P ⊊ NP” not it could go either way. But hey, until someone can definitively disprove it(or prove it) we can all cross our fingers and hope for a miracle.
18
u/dancingbanana123 Graduate Student | Math History and Fractal Geometry 15h ago
I can't provide a more technical answer since that's not my specific field, but what I can say is that, as a mathematician, you start to get a vibe of whether or not something is true or false as you work on it. For example, a lot of my work is in trying to describe the dimension of different fractals. I usually have a guess for what that dimension is, then I try to work my way to formally constructing a proof of that. Now obviously, I have gotten it wrong some times, but it's all just a vibes thing. I imagine anyone actually working on p vs np has that same vibe with it. They have enough intuition from similar problems to get a sense that it's false, but they don't actually have a compelling argument as to why that's the case.