399. What would happen if P = NP?
MediumComplexity classes
Show model answer
Every problem whose solutions can be checked quickly could also be solved in polynomial time: SAT, scheduling, routing, protein folding models and finding short proofs of theorems. One-way functions could not exist, so public-key cryptography based on hard problems, such as RSA, would lose its theoretical security foundation. The whole polynomial hierarchy would collapse to P.
The practical impact depends on the algorithm: an O(n^100) algorithm or a non-constructive proof would change theory far more than practice. Most researchers believe P ≠ NP. Meanwhile, NP-hard problems are handled with approximation algorithms, fixed-parameter algorithms, heuristics, SAT/ILP solvers and exponential algorithms tuned for real instance sizes.