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
> 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.
Someone is overstating their case. NP hard problems are going to be algorithmic, so they’re basically math problems. You may be able to use algorithms to find a cure for cancer, but cancer is not an NP hard problem.
An NP hard problem is going to be something like the knapsack problem. Let’s say you have a bunch of objects that each have a weight and a value. Can you get V value without exceeding weight W? We don’t know if there is an algorithm that can solve this quickly if we had say thousands or millions of objects to consider.
Another one is the traveling salesman problem. If we have a map of cities and those cities have distances between them, what is the shortest route that visits every city and returns to the start? Again, we don’t know if there is an algorithm that can solve this quickly if we have a lot of cities.
But, we do know that if we solve this problem, we will also have a solution to the knapsack problem, because there is a way to turn a knapsack problem into a traveling salesman problem. That’s how we know a problem is NP hard. If we can turn it into another NP hard problem.
Latest Answers