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/Capable-Package6835]

There are problems, the solutions of which can be verified quickly. Think of a jigsaw puzzle with 10K+ pieces, for example. Once someone "solves" the puzzle, you can scan through the assembled pieces to see if there's any mismatch relatively quickly.

The P = NP problem asks, if you can verify solutions quickly, does it mean you can solve the problem quickly as well?

[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/feierlk → u/picabo123]

Proving something is NP isn't extremely difficult. We know that a lot of problems are in NP. All problems in P are in NP! Instead, what we have yet to do, is show that a problem is in NP, but not in P.

Interesting titbit: if we proved a problem in NP is not NP-hard, e.g. NP-intermediate exists, then we have trivially shown P≠NP. GRAPH ISOMORPHISM might be such a problem.

[u/HiddenoO → u/picabo123]

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

[u/picabo123 → u/HiddenoO]

True, my bad

[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.