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
Within the class of problems known as “NP” there is a class of problems known as “NP-Complete” which essentially have, as part of their definition, the requirement (or consequence) that any one NP-complete problem can be transformed into any other NP-complete problem. So if you have a solution to one of them, then all you have to do is apply that transformation: take an NP-complete problem you don’t have a solution to, transform it into one you do and then apply the solution.
There is a group of problems which each of them has been proven that every problem which can be solved in NP time can be converted into that problem in polynomial time.
so if P = NP, you can convert any problem into one of those problems and then solve it in polynomial time.
> 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.
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.
> but that doesn’t mean there’s a universal “key” that magically solves all NP problems in polynomial time.
Yes, there is. An NP problem, by its definition, can be solved by a *nondeterministic* Turing machine in polynomial time. Such machines only exist on paper (any actual non-quantum computer is a *deterministic* machine), but they *do* exist on paper and can be described in a mathematical way.
Turning the description of an NP-problem into a corresponding description of a nondeterministic Turing machine can be done in polynomial time. In a similar way, any description of a nondeterministic Turing machine can be turned into a Boolean expression which is true if and only if the machine runs successfully on the input. Again, this transformation can be done in polynomial time.
Now, finding an input that makes a given Boolean expression true is known as the satisfiability, or SAT problem, which is itself proven to be an NP problem. So, if you find an algorithm to solve the SAT problem in polynomial time with a deterministic Turing machine (the definition of a P problem), you can for any NP problem:
– construct its nondeterministic Turing machine in polynomial time
– construct the corresponding Boolean expression in polynomial time
– solve the SAT problem with a deterministic Turing machine in polynomial time.
which means that in the end you will have solved the NP problem in polynomial time with a deterministic Turing machine, making it a P problem. Again, this approach works for any NP problem.
There are range of other NP problems like the knapsack problem where there is a polynomial algorithm to transform the SAT problem into those problems in polynomial time, so finding a polynomial-deterministic solution to any of these problems would likewise solve all NP problems in polynomial time (first transform the problem to SAT, and then transform SAT to knapsack). These problems are collectively known as NP-complete problems.
Now mind you that even a polynomial-time algorithm is not necessarily fast (after all, Bubble sort and Gnome sort are polynomial algorithms too), but for large enough inputs it will be faster than the most efficient exponential algorithms.
> 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.
> 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.
These are not good examples. Predicting the weather with complete accuracy is impossible in practice due to chaos – any tiny initial error grows exponentially with time and since initial errors will always exist. It has nothing to do with the P vs NP problem, and curing cancer is not a mathematical problem at all (there may be some mathematical problems in that field that are relevant, though).
Only cracking encryption is relevant, because the security of many modern encryption algorithms depends on the unproven assumption that certain problems are effectively impossible to solve in practice, and a proof of P=NP would undermine that assumption.
NP problems, strictly speaking, are decision problems – they have a yes or no answer. Many well known problems can be restated as decision problems – for example, the famous travelling salesman problem, which asks for the shortest route that visits all nodes of a graph, can be made into a decision problem by asking “is there a route shorter than L”.
Also, NP does not mean “hard to solve” – all problems that are in P are also in NP, including some trivial ones like the problem of determining whether a given number is even. The hardest problems in NP are termed “NP-complete” – it has been shown that these problems are at least as hard as all problems in NP – so if an NP-complete problem was found to be in P, then P=NP.
> 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?
Problems in P are solvable in polynomial time. If it was proven that P=NP, that means all the problems in NP can also be solved in polynomial time, including many for which the fastest known algorithms require exponential time. That would be a huge result. But, a proof of P=NP need not be a constructive proof – that is, it wouldn’t necessarily tell us *how* to solve these problems in polynomial time, only that it is possible.
Also, x^100000000000 is still a polynomial. Proving that P=NP means a polynomial time algorithm exists, which for large enough inputs would be faster than any algorithm currently known – but it might be that the new polynomial time algorithm is only faster for inputs larger than what we can feasibly process already.
Latest Answers