Nondeterministic algorithm - Revision history

David Eppstein: /* top */ ce

2024-07-07T06:28:21Z

top: ce

← Previous revision		Revision as of 06:28, 7 July 2024
Line 4:		Line 4:
	Different [[model of computation\|models of computation]] give rise to different reasons that an algorithm may be non-deterministic, and different ways to evaluate its performance or correctness:		Different [[model of computation\|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 [[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 algorithm]], ~~where~~ (like concurrent algorithms) all runs must produce correct output, and [[Monte Carlo algorithm]]s 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]].		*A [[probabilistic algorithm]]'s behavior depends on a [[random number generator]] called by the algorithm. These are subdivided into [[Las Vegas algorithm]]s, for which (like concurrent algorithms) all runs must produce correct output, and [[Monte Carlo algorithm]]s 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 class]]es 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]].		*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 class]]es 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]].

David Eppstein: /* top */ tighter

2024-07-07T06:25:28Z

top: tighter

← Previous revision		Revision as of 06:25, 7 July 2024
Line 5:		Line 5:
	*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 [[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 algorithm]], where (like concurrent algorithms) all runs must produce correct output, and [[Monte Carlo algorithm]]s 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]].		*A [[probabilistic algorithm]]'s behavior depends on a [[random number generator]] called by the algorithm. These are subdivided into [[Las Vegas algorithm]], where (like concurrent algorithms) all runs must produce correct output, and [[Monte Carlo algorithm]]s 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 ''there exists'' a ~~sequence of nondeterministic choices~~ that it ~~could~~ ~~make that lead it to a correct~~ result, even when ~~most or all~~ other ~~choice~~ 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 class]]es 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]].		*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 class]]es 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]].

	The notion of nondeterminism was introduced by [[Robert W. Floyd]] in 1967.<ref>		The notion of nondeterminism was introduced by [[Robert W. Floyd]] in 1967.<ref>

David Eppstein: I think it's really all the same thing; rewrite to emphasize the commonality of these ideas, and incorporate the see-also links into the text

2024-07-07T06:23:54Z

I think it's really all the same thing; rewrite to emphasize the commonality of these ideas, and incorporate the see-also links into the text

@@ Line 1: / Line 1: @@
 {{short description|Algorithm whose behavior and output may depend on the run}}
-The notion was introduced by [[Robert W. Floyd]] in 1967.<ref>
+The notion of nondeterminism was introduced by [[Robert W. Floyd]] in 1967.<ref>
 {{cite journal
 | title = Nondeterministic Algorithms
@@ Line 18: / Line 20: @@
 | doi-access = free
 }}</ref>
 ==References==

OAbot: Open access bot: doi updated in citation with #oabot.

2023-08-24T09:21:22Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 09:21, 24 August 2023
Line 16:		Line 16:
	\| doi = 10.1145/321420.321422		\| doi = 10.1145/321420.321422
	\| s2cid = 1990464		\| s2cid = 1990464
			\| doi-access = free
	}}</ref>		}}</ref>

D.Lazard: /* See also */ The article title has changed

2023-04-16T16:35:32Z

AnomieBOT: Dating maintenance tags: {{Confusing}}

2022-01-30T16:32:57Z

Dating maintenance tags: {{Confusing}}

← Previous revision		Revision as of 16:32, 30 January 2022
Line 1:		Line 1:
	{{short description\|Algorithm whose behavior and output may depend on the run}}		{{short description\|Algorithm whose behavior and output may depend on the run}}
	{{about\|nondeterminism in [[computer programming]]\|nondeterminism in [[computational complexity theory]]\|Nondeterministic model of computation}}		{{about\|nondeterminism in [[computer programming]]\|nondeterminism in [[computational complexity theory]]\|Nondeterministic model of computation}}
	{{Confusing\|reason=the word "nondeterministic" is used with two different meanings\|talk=Talk:Nondeterministic algorithm#Misleading Article}}		{{Confusing\|reason=the word "nondeterministic" is used with two different meanings\|talk=Talk:Nondeterministic algorithm#Misleading Article\|date=January 2022}}

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

JonH: add confusing template

2022-01-30T16:12:46Z

add confusing template

← Previous revision		Revision as of 16:12, 30 January 2022
Line 1:		Line 1:
	{{short description\|Algorithm whose behavior and output may depend on the run}}		{{short description\|Algorithm whose behavior and output may depend on the run}}
	{{about\|nondeterminism in [[computer programming]]\|nondeterminism in [[computational complexity theory]]\|Nondeterministic model of computation}}		{{about\|nondeterminism in [[computer programming]]\|nondeterminism in [[computational complexity theory]]\|Nondeterministic model of computation}}
			{{Confusing\|reason=the word "nondeterministic" is used with two different meanings\|talk=Talk:Nondeterministic algorithm#Misleading Article}}

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

Citation bot: Add: s2cid. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

2021-11-15T04:26:28Z

Add: s2cid. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

← Previous revision		Revision as of 04:26, 15 November 2021
Line 14:		Line 14:
	\| pages = 636–644		\| pages = 636–644
	\| doi = 10.1145/321420.321422		\| doi = 10.1145/321420.321422
			\| s2cid = 1990464
	}}</ref>		}}</ref>

D.Lazard: /* top */ fixing two links

2021-03-01T11:31:55Z

top: fixing two links

← Previous revision		Revision as of 11:31, 1 March 2021
Line 1:		Line 1:
	{{short description\|Algorithm whose behavior and output may depend on the run}}		{{short description\|Algorithm whose behavior and output may depend on the run}}
	{{about\|nondeterminism in [[programming]]\|nondeterminism in [[computational complexity theory]]\|Nondeterministic model of computation}}		{{about\|nondeterminism in [[computer programming]]\|nondeterminism in [[computational complexity theory]]\|Nondeterministic model of computation}}

	In [[computer ~~science~~]], 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.		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.

	The notion was introduced by [[Robert W. Floyd]] in 1967.<ref>		The notion was introduced by [[Robert W. Floyd]] in 1967.<ref>

D.Lazard: /* top */ clearer hatnote

2021-03-01T11:30:25Z

top: clearer hatnote

← Previous revision		Revision as of 11:30, 1 March 2021
Line 1:		Line 1:
	{{short description\|Algorithm whose behavior and output may depend on the run}}		{{short description\|Algorithm whose behavior and output may depend on the run}}
	{{about\|~~algorithms~~ ~~whose~~ ~~behavior and output may depend on the run~~\|~~models of computation where many~~ ~~choices~~ ~~are~~ ~~considered~~ ~~simultaneously~~\|Nondeterministic model of computation}}		{{about\|nondeterminism in [[programming]]\|nondeterminism in [[computational complexity theory]]\|Nondeterministic model of computation}}

	In [[computer science]], 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.		In [[computer science]], 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.

← Previous revision		Revision as of 16:35, 16 April 2023
Line 33:		Line 33:

	==See also==		==See also==
	* [[~~Non-deterministic~~ Turing machine]]		* [[Nondeterministic Turing machine]]
	* [[Nondeterministic programming]]		* [[Nondeterministic programming]]