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.
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