I’ve fallen down a YouTube/internet rabbit hole of videos on the [P vs NP](https://news.mit.edu/2009/explainer-pnp#:~:text=Roughly%20speaking%2C%20P%20is%20a,actually%20have%20relatively%20easy%20solutions) problem. The content I’ve watched seems to imply that, if it’s finally proven that P = NP, then there will be a common way to solve all NP problems. One of the articles I read said (I’m paraphrasing here) that if P = NP, then there will be a “shortcut” to solve all NP problems.
Examples given of NP problems have varied widely…from figuring out a cure for cancer, to cracking any encryption code known to man, to predicting the weather with 100% accuracy. Those problems are all vastly different, all come from different domains of knowledge/science, and all have radically different solutions.
So if P = NP, how do we know or why do we assume there will be some sort of shortcut that makes solving these problems easier? I totally get that P = NP means that NP problems have a way to make them easier to solve…but that doesn’t mean there’s a universal “key” that magically solves all NP problems in polynomial time. Or…is proving this part of solving the overall assertion?
In: 1
If we find a polynomial solution to a problem which is currently considered NP, but not NP-complete, this problem would be moved to P. Nothing else happen.
If we find a polynomial solution to a problem which is currently considered NP-complete, this problem and every NP would be moved to P, so P=NP. There’s no reason to believe that’s possible to do. We just can’t prove that’s not the case.
If we find a polynomial solution to a problem which is NP-hard but doesn’t have a NP solution right now, this problem and every NP would be moved to P, so P=NP. There’s no reason to believe that’s possible to do. We just can’t prove that’s not the case. Other NP-hard problems will remain NP-hard.
NP problems: problems that could be solved in polynomial time with perfect luck. In practice, they are solved in exponential time.
NP-hard problems: problems that any NP-problems can be transformed into in polynomial time. If one of them is solvable in polynomial time, any NP problem is solvable in polynomial time. NP-hard problems are not necessarily NP.
NP-complete: problems that are both NP and NP-hard.
Of the list of applications you have, only decrypting encryption is an actual NP problem.
Latest Answers