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