Metraipolis › archive › dc_533ca1ceb6fe

Nondeterministic algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Nondeterministic_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T18:26:56.314Z
SHA-256 of the archived text
4f93aceae259c39b3352f1c9188fa93ee6ecf92a1cdaf827a196d1daa8108197
Stable URL of this page
https://metraipolis.com/documento/dc_533ca1ceb6fe

How to cite

Nondeterministic algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Nondeterministic_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_533ca1ceb6fe (Metraipolis archive dc_533ca1ceb6fe, sha256 4f93aceae259c39b3352f1c9188fa93ee6ecf92a1cdaf827a196d1daa8108197)
BibTeX
@misc{dc533ca1ceb6fe,
  title = {Nondeterministic algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Nondeterministic_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_533ca1ceb6fe; sha256 4f93aceae259c39b3352f1c9188fa93ee6ecf92a1cdaf827a196d1daa8108197},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Nondeterministic_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In computer science and computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. Different models of computation give rise to different reasons that an algorithm may be non-deterministic, and different ways to evaluate its performance or correctness: A concurrent algorithm can perform differently on different runs due to a race condition. This can happen even with a single-threaded algorithm when it interacts with resources external to it. In general, such an algorithm is considered to perform correctly only when all possible runs produce the desired results. A probabilistic algorithm's behavior depends on a random number generator called by the algorithm. These are subdivided into Las Vegas algorithms, for which (like concurrent algorithms) all runs must produce correct output, and Monte Carlo algorithms which are allowed to fail or produce incorrect results with low probability. The performance of such an algorithm is often measured probabilistically, for instance using an analysis of its expected time. In computational complexity theory, nondeterminism is often modeled using an explicit mechanism for making a nondeterministic choice, such as in a nondeterministic Turing machine. For these models, a nondeterministic algorithm is considered to perform correctly when, for each input, there exists a run that produces the desired result, even when other runs produce incorrect results. This existential power makes nondeterministic algorithms of this sort more efficient than known deterministic algorithms for many problems. The P versus NP problem encapsulates this conjectured greater efficiency available to nondeterministic algorithms. Algorithms of this sort are used to define complexity classes based on nondeterministic time and nondeterministic space complexity. They may be simulated using nondeterministic programming, a method for specifying nondeterministic algorithms and searching for the choices that lead to a correct run, often using a backtracking search.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Nondeterministic algorithm» — https://en.wikipedia.org/wiki/Nondeterministic_algorithm
Wikidata Q3490301: «model in computer science» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q3490301
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Nondeterministic_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1321099803, consultata il 2026-10-07T17:55:30.506Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 7a17841ad9fbf2ec396874ec03d292416027f4ab5c7b9ffef921be747411250f