If the problem of P vs NP is proved that p = np, how would that affect AI advancements?
I understand that the problem would cause many things to change within our technology, but what sort of changes would we expect to see with AI specifically?
In: 0
> If the problem of P vs NP is proved that p = np
That’s a big if. Most people suspect they aren’t the same.
Anyway, it’s difficult to say anything about the practical implications. If P=NP, then this implies that many known problems can be solved by algorithms that outperform any known algorithms *for instances of the problem that are large enough*. We don’t know how large that “large enough” would be. We don’t even know if a proof that P=NP would lead to usable algorithms.
It’s quite common for people to come up with “non-constructive” proofs that tell you something is possible without telling you how to do it. It’s also quite common for people to prove that it’s possible to solve a problem by providing an algorithm that technically works but is not actually useful. A simple example of that is Euclid’s proof that there are infinitely many prime numbers. This proof works by constructing an algorithm that is guaranteed to be able to give you a larger prime number than any you have found so far. However, this algorithm is *wildly* inefficient, even by Ancient Greek standards. A more advanced example in a very similar context is the AKS algorithm. The existence of this algorithm proved that the problem of checking whether a number is prime is in P. However, in practice, it was not more useful than existing algorithms (all of which failed to prove that the problem was in P, either because they did not work for all numbers, or only gave approximate answers, or were not known to be polynomial).
> how would that affect AI advancements
NP-complete problems often do come up in machine learning. But it’s very difficult to say how a proof of P=NP would influence the field. There are just too many unknowns.
Latest Answers