May 2019
Intermediate to advanced
698 pages
17h 21m
English
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).
Read now
Unlock full access