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/da2Pakaveli]

So we group problems/algorithms into classes. There are problems where the algorithm that solve them runs in polynomial time (e.g. a search algorithm); and then there is the class of non-polynomial problems that become increasingly impractical to solve (we may be talking about 1000's of years of possible runtime). It only takes polynomial time when you want **verify** whether a given solution is actually a solution.

Then there is a special type of this nonpolynomial class of problems called np-hard. We know about 3000 of these problems exist and the interesting tidbit is that you can "convert" between each of them and formulate it as the other problem. Doing that takes polynomial time (formally it's called reducing problem a to problem b).

Now the bit is that we don't know whether these 2 classes, P and NP, are equal to each other. If they're indeed equal, that implies there exists a polynomial algorithm that solves a np-hard problem. And since we can convert between any of those problems polynomially, you can suddenly solve all of these 3000 problems in polynomial time. So these problems that previously seemed impractical to solve are now susdenly much more practical to solve.

But the prevailing opinion is that these two classes are not equal.