Hands-On Data Structures and Algorithms with Rust

Exotic things

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. ...