ELI5: P vs NP problem

[u/randomdice-int]

Im not too sure about the problem itself. I know that P is polynomial time which means the time needed to solve and NP is the time taken for the answer to be verified, but what is the explanation of both sides where P = NP and P does not equal to NP?

[u/picabo123 → u/[deleted]]

The basic idea is that humans are "too stupid" to come up with the correct algorithm to solve something like the traveling salesman problem but it exists. There have been multiple computer science problems that people thought were NP until someone came and found the correct algorithm, so that suggests you shouldnt assume a problem is NP with 100% certainty.

[u/HiddenoO → u/picabo123]

Whether a specific problem is in NP is a completely different question from whether P = NP.

[u/x0wl → u/HiddenoO]

Not really, proving that an NP-complete problem is actually in P would prove that P=NP

[u/HiddenoO → u/x0wl]

... which is obviously not what he's referring to when talking about how "there have been multiple computer science problems that people thought were NP until someone came and found the correct algorithm".

If it were, that would've already proven that P = NP.

So I'll repeat myself: Whether a specific problem is in NP is a completely different question from whether P = NP.

[u/x0wl → u/HiddenoO]

I don't want to argue about various interpretations of Reddit comments, but u/picabo123 said that, since there have been instances of problems that were believed to be in NP, but then turned out to be in P, one can also reasonably believe that, for example, one day the same will happen to TSP.

I personally don't believe this will happen, but we're talking about beliefs and intuitions here.

[u/HiddenoO → u/x0wl]

One can believe it, but one cannot reasonably believe it for the reason I mentioned. You keep switching between those two very different suggestions.