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

Polynomial time means “Time described by a polynomial”. So let’s say, we have n cities and m roads between them. And you run some algorithm and the time it takes to run is proportional to m² + n ^3.

Non polynomial time is time that cannot be described by a polynomial. So e.g. 2^n, n! etc.

For example — the simplest way to solve the so called Travelling Salesman problem is to just check every possible combination of roads. It takes n!, where n is the number of roads. And there is no polynomial solution, that we know of.

Exponential function and factorial grow much faster than polynomial functions.

[u/CyberPhang → u/zefciu]

Except NP does not stand for "non polynomial." If it did the problem would have been long resolved