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
> that if P = NP, then there will be a “shortcut” to solve all NP problems
This is a bit of a nitpick, but the P vs NP problem is about a very specific statement regarding how the number of steps needed to solve a problem grows as the size of the input data grows. As a general rule, NP-hard problems are “difficult” and problems in P are “easy”, but there are specific instances of NP-hard problems that can be dealt with easily, and there are specific instances of problems in P that are intractable. As a simple example, “sort this list of n numbers into ascending order” is in P, but if n is absolutely massive (say, 1000000000000000000000000000000000000), then we can’t do it.
So even if P=NP, it isn’t necessarily the case that we will suddenly be able to solve all NP-hard problems very easily. Conversely, even if P≠NP, there might be some undiscovered shortcuts that would make it substantially easier to solve NP-hard problems. In other words, the question of whether P=NP is only part of the issue, but it’s expected that if someone does resolve that specific question, then the manner in which it is resolved will shed light on the surrounding questions.
> 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.
The kinds of problems that we’re interested in here are “decision problems”. These are problems in which we have some well-defined statement about some data and we want to know whether it’s true or not. For example, “Given a number n, is n prime?” is a decision problem. “Given a specific network of roads and a distance d, is there a route that travels along all of the roads covering a total distance less than d?” is also a decision problem.
Curing cancer, cracking any and all encryption algorithms, and predicting the weather are not decision problems. They are much too vague and open-ended. So it doesn’t make sense to talk about which complexity class they are in. There may be many specific decision problems that come up when researching these problems, but these will be in a variety of different complexity classes.
> 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?
There is a class of problems called “NP-complete” problems. These are problems that are in NP, and which any other problem in NP can be reduced to “quickly” (in polynomial time). Many specific problems have been shown to be NP-complete. However, the above disclaimer about what “quickly” means still applies. Even if P=NP, and even if one specific instance of an NP-complete problem is tractable, that doesn’t mean all instances of all problems in NP must be tractable.
Latest Answers