P Versus NP Complexity
The P Versus NP issue deals with whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. This is a major unsolved problem in computer science.
In common, practical terms, it deals with how to identify problems that are either extremely difficult or impossible to solve. In order of difficulty from easy to hard, problems are classified as:
So why do we care? When approaching complex problems, it's useful to have at least some idea of whether the problem is precisely solvable, or if an approximation is the best that can be accomplished. Many Machine Learning and AI Applications deal with problems of high complexity.