One class that was omitted from the earlier list is polynomial time (P in short). This class is quicker to solve than the exponential time class, but worse than O(n²). These problems include checking whether a number is a prime number, or solving a Sudoku. However, there are other problems in this class as well that actually have no "quick" (that is, solvable in P) solution, but a solution can be verified in P time. These are called NP (an abbreviation of non-deterministic polynomial time) problems and the hardest of them are NP-hard (see the information box).
The distinction between P, NP, NP-complete, and NP-hard is not intuitive. NP problems are problems that can be solved using a non-deterministic Turing machine in P time. NP-hard problems are problems without a solution that, if solved, would have a polynomial time solution and if it is also an NP problem, it is also considered NP-complete. Additionally, finding a solution for one of either class (NP...
