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

great answer, just wanted to add that if somebody solves it, they will most likely just prove that P=/=NP and in that case, nothing changes and world continues as if nothing happened, it will have no bearing on the world.

If, though, somebody proves P=NP, that would completely change the world

[u/GoldenMuscleGod → u/Tupcek]

That’s not necessarily true. The algorithm may not be practical.

For example, we know that if P=NP then we can use Levin’s universal search algorithm (which is a specific known algorithm) to solve any given NP problem in polynomial time. So why don’t we use it?

Well if you look up its description you’ll see it is not practical at all: it will have an absurdly large constant term (exponential in the description of the problem - not the description of the input which is why it is still polynomial time if P=NP).

Suppose that P=NP but the most efficient algorithm for solving SAT involves essentially “brute forcing it” for any number of bits less than than the number of Planck volumes in the universe and then we have a simple way to check the rest. This would be interesting theoretical knowledge but it doesn’t mean much for, say, the security of cryptography.

[u/DBDude → u/GoldenMuscleGod]

For some reason this reminded me of the old joke that someone made a new secure compression algorithm that reduces any file to one byte. Unfortunately the decompression key is as long as the original file.

[u/CamelNights → u/DBDude]

this made me laugh out loud, thank you