P v NP is a misleading scholastic question. It talks about “worst case” performance -that is, a performance on a hardest problem of certain type. So, a traveling salesman problem (finding a shortest path through a set of towns) is NP-complete, does it mean that all of us are unable to plan our day with 3 stops? of course not. A relevant theory is “average case” performance – how long does it take to solve an average problem of this type. Many modern algorithms, including AI/machine learning, are built in this way (some explicitly, most implicitly) – solving typical problems fast, even if theoretical hardest problems are not solvable.
Menu