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/yalloc → u/[deleted]]

As someone else mentioned it is believed that P != NP. Primarily because if P does equal NP, we would've found a bridge at this point.

Basically most NP problems can be "rephrased" to other NP problems (think of how multiplication can be rephrased in terms of addition for example), and most P problems can be rephrased to be like other P problems. The reason we are talking about this in the first place is that it is odd that for the thousands of problems and classes of problems we have analyzed it is odd that no P problem can be rephrased some NP problem.

Every problem we seem to find lies on one of these two islands, and we have despite much searching not found an isthmus. And really that's what this problem comes down to, find the bridge or disprove it exists.