Non-deterministic algorithms
Non-deterministic algorithms are theoretical constructs used primarily in the study of computational complexity. They assume the existence of a “non-deterministic” machine, such as a non-deterministic Turing machine, which can make arbitrary choices to explore different computational paths simultaneously. Non-deterministic algorithms are often used to define classes of problems, such as nondeterministic polynomial time (NP), which includes problems for which a solution can be verified in polynomial time by a deterministic algorithm. Non-deterministic algorithms are not practically implementable on standard deterministic machines. They serve as a way to understand the potential power of parallel computation and to classify problem complexity.
Note
Non-deterministic algorithms are not practically implementable on standard deterministic machines. Randomized algorithms, on the other hand, are practical algorithms that use random numbers...
