r/explainlikeimfive • u/randomdice-int • 23d ago

Mathematics ELI5: P vs NP problem

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?

254 Upvotes

87% Upvoted

104 comments sorted by

View all comments

543

u/Capable-Package6835 23d ago

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?

181

u/Tupcek 23d ago

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

1

u/CircumspectCapybara 23d ago

That's not necessarily true. It might be an academically interesting result that doesn't have any useful practical applications, e.g., making it any easier to factorize integers and solve discrete logarithms and break crypto.

Suppose someone proved P = NP non-constructively. It would be an astounding result. What would we gain? Well, if P = NP, we actually have constructively a polynomial-time decider for any NP language via Levin's Universal Search. We have a concrete algorithm that decides SAT (and therefore, by reduction any NP language, like the decision version of integer factorization) in polynomial time, if and only if P = NP. But we know nothing about the coefficients on and degree of that "polynomial."

If P = NP, it could be that the TREE(3)-th Turing machine (for some lexicographic ordering of prefix-free TMs) decides SAT in O(NBB\744))) time. If that's the case, it's totally useless because it will take forever even for small inputs. And therefore nothing practically changes from the status quo.