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