Nondeterministic algorithm
In 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. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one.
- Comment
- enIn 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. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one.
- Date
- enJanuary 2022
- Has abstract
- enIn 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. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one. The notion was introduced by Robert W. Floyd in 1967.
- Hypernym
- Algorithm
- Is primary topic of
- Nondeterministic algorithm
- Label
- enNondeterministic algorithm
- Link from a Wikipage to an external page
- cs.nyu.edu/courses/spring03/G22.2560-001/nondet.html
- xlinux.nist.gov/dads/HTML/nondetermAlgo.html
- Link from a Wikipage to another Wikipage
- Algorithm
- Category:Computational complexity theory
- Category:Theory of computation
- Computational complexity theory
- Computational theory
- Computer programming
- Concurrent algorithm
- Deterministic algorithm
- Finite automata
- Models of computation
- Nondeterministic finite automaton
- Nondeterministic polynomial time
- Nondeterministic programming
- Non-deterministic Turing machine
- Powerset construction
- Probabilistic
- Probabilistic algorithm
- P vs NP
- Race condition
- Randomized algorithm
- Random number generator
- Robert W. Floyd
- Search algorithm
- Reason
- enthe word "nondeterministic" is used with two different meanings
- SameAs
- 3Dftd
- Algoritm minga deterministich
- Algoritmo não determinístico
- Algoritmo no determinista
- m.031354
- Nedeterministický algoritmus
- Nichtdeterminismus
- Nondeterministic algorithm
- Q3490301
- Thuật toán không đơn định
- Недетермінований алгоритм
- الگوریتم غیرقطعی
- 비결정론적 알고리즘
- Subject
- Category:Computational complexity theory
- Category:Theory of computation
- Talk
- enTalk:Nondeterministic algorithm#Misleading Article
- WasDerivedFrom
- Nondeterministic algorithm?oldid=1068881574&ns=0
- WikiPageLength
- 4849
- Wikipage page ID
- 665957
- Wikipage revision ID
- 1068881574
- WikiPageUsesTemplate
- Template:About
- Template:Cite book
- Template:Cite web
- Template:Confusing
- Template:Reflist
- Template:Short description