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
It would go far beyond AI advancements. But the P vs NP thing is a matter of “computability over time vs verifiability of a computation over time”
**The ELI5 Version would be something like this:**
There are instructions that you can give a computer that in order to finish and come up with the answer will require time greater than the lifespan of the sun in our solar system. If a given problem cannot be solved quickly but the solution can be verified quickly we call it NP. If it can be solved quickly we call it P.
To my fellow math nerds, this is a gross simplification and I apologize.
**The more elaborate answer:**
Basically can a computer compute a set of given instructions in a finite amount of time. Different problems and the size of their datasets factor in to P or NP classification significantly.
A good starting point for understanding the mathematics that can drive P vs NP problems is Big O Notation, which describe factors that limit functions when an argument of that function points to a particular high bound value or infinity.
[https://en.wikipedia.org/wiki/Big_O_notation](https://en.wikipedia.org/wiki/Big_O_notation)
There are also problems that we classify as NP but that we have “heuristic” solutions for. Where an approximation or non deterministic answer is deemed acceptable. Think traveling salesman or route optimization.
This an example of a P problem that was optimized heuristically, and has kind of a cool story behind it involving the development of Quake.
https://en.wikipedia.org/wiki/Fast_inverse_square_root
> 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