Randomized algorithm - Revision history

WikiCleanerBot: v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2025-02-19T18:46:59Z

v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 18:46, 19 February 2025
Line 159:		Line 159:
	{{Unreferenced\|section\|date=September 2023}}		{{Unreferenced\|section\|date=September 2023}}

	Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible)<ref>{{Cite web \|title=6.046J Lecture 22: Derandomization {{!}} Design and Analysis of Algorithms {{!}} Electrical Engineering and Computer Science \|url=https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/ \|access-date=2024-12-27 \|website=MIT OpenCourseWare \|language=en}}</ref><ref>{{Cite report \|url=https://dl.acm.org/doi/10.5555/894682 \|title=Pairwise Independence and Derandomization \|last1=Luby \|first1=Michael \|last2=Wigderson \|first2=Avi \|date=July 1995 \|publisher=University of California at Berkeley \|location=USA}}</ref>. It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time<ref name=":2">{{Cite web \|title=Lecture Notes, Chapter 3. Basic Derandomization Techniques \|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm \|access-date=2024-12-27 \|website=people.seas.harvard.edu}}</ref>. For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]]<ref name=":2" />, i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.		Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible).<ref>{{Cite web \|title=6.046J Lecture 22: Derandomization {{!}} Design and Analysis of Algorithms {{!}} Electrical Engineering and Computer Science \|url=https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/ \|access-date=2024-12-27 \|website=MIT OpenCourseWare \|language=en}}</ref><ref>{{Cite report \|url=https://dl.acm.org/doi/10.5555/894682 \|title=Pairwise Independence and Derandomization \|last1=Luby \|first1=Michael \|last2=Wigderson \|first2=Avi \|date=July 1995 \|publisher=University of California at Berkeley \|location=USA}}</ref> It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time.<ref name=":2">{{Cite web \|title=Lecture Notes, Chapter 3. Basic Derandomization Techniques \|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm \|access-date=2024-12-27 \|website=people.seas.harvard.edu}}</ref> For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]],<ref name=":2" /> i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.

	There are specific methods that can be employed to derandomize particular randomized algorithms:		There are specific methods that can be employed to derandomize particular randomized algorithms:

Citation bot: Altered title. Add: authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Jay8g | Category:CS1 errors: DOI | #UCB_Category 2/3

2024-12-27T21:32:55Z

Altered title. Add: authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Jay8g | Category:CS1 errors: DOI | #UCB_Category 2/3

← Previous revision		Revision as of 21:32, 27 December 2024
Line 81:		Line 81:

	=== Implicit uses in combinatorics ===		=== Implicit uses in combinatorics ===
	Prior to the popularization of randomized algorithms in computer science, [[Paul Erdős]] popularized the use of randomized constructions as a mathematical technique for establishing the existence of mathematical objects. This technique has become known as the [[probabilistic method]].<ref name=":1">{{Cite book \|~~last~~=Alon \|~~first~~=Noga \|title=The probabilistic method \|date=2016 \|first2=Joel H. \|last2=Spencer \|isbn=978-1-119-06195-3 \|edition=Fourth \|publisher=Wiley \|location=Hoboken, New Jersey \|oclc=910535517}}</ref> [[Paul Erdős\|Erdős]] gave his first application of the probabilistic method in 1947, when he used a simple randomized construction to establish the existence of Ramsey graphs.<ref>P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. '''53''' (1947), 292--294 '''MR'''8,479d; '''Zentralblatt''' 32,192.</ref> He famously used a more sophisticated randomized algorithm in 1959 to establish the existence of graphs with high girth and chromatic number.<ref>{{Cite journal \|last=Erdös \|first=P. \|date=1959 \|title=Graph Theory and Probability \|journal=Canadian Journal of Mathematics \|language=en \|volume=11 \|pages=34–38 \|doi=10.4153/CJM-1959-003-9 \|s2cid=122784453 \|issn=0008-414X\|doi-access=free }}</ref><ref name=":1" />		Prior to the popularization of randomized algorithms in computer science, [[Paul Erdős]] popularized the use of randomized constructions as a mathematical technique for establishing the existence of mathematical objects. This technique has become known as the [[probabilistic method]].<ref name=":1">{{Cite book \|last1=Alon \|first1=Noga \|title=The probabilistic method \|date=2016 \|first2=Joel H. \|last2=Spencer \|isbn=978-1-119-06195-3 \|edition=Fourth \|publisher=Wiley \|location=Hoboken, New Jersey \|oclc=910535517}}</ref> [[Paul Erdős\|Erdős]] gave his first application of the probabilistic method in 1947, when he used a simple randomized construction to establish the existence of Ramsey graphs.<ref>P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. '''53''' (1947), 292--294 '''MR'''8,479d; '''Zentralblatt''' 32,192.</ref> He famously used a more sophisticated randomized algorithm in 1959 to establish the existence of graphs with high girth and chromatic number.<ref>{{Cite journal \|last=Erdös \|first=P. \|date=1959 \|title=Graph Theory and Probability \|journal=Canadian Journal of Mathematics \|language=en \|volume=11 \|pages=34–38 \|doi=10.4153/CJM-1959-003-9 \|s2cid=122784453 \|issn=0008-414X\|doi-access=free }}</ref><ref name=":1" />

	==Examples==		==Examples==
Line 159:		Line 159:
	{{Unreferenced\|section\|date=September 2023}}		{{Unreferenced\|section\|date=September 2023}}

	Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible)<ref>{{Cite web \|title=6.046J Lecture 22: Derandomization {{!}} Design and Analysis of Algorithms {{!}} Electrical Engineering and Computer Science \|url=https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/ \|access-date=2024-12-27 \|website=MIT OpenCourseWare \|language=en}}</ref><ref>{{Cite report \|url=https://dl.acm.org/doi/10.5555/894682 \|title=Pairwise Independence and Derandomization \|~~last~~=Luby \|~~first~~=Michael \|last2=Wigderson \|first2=Avi \|date=July 1995 \|publisher=University of California at Berkeley ~~\|doi=10.5555/894682~~ \|location=USA}}</ref>. It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time<ref name=":2">{{Cite web \|title=Lecture Notes, Chapter 3. Basic Derandomization Techniques, \|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm \|access-date=2024-12-27 \|website=people.seas.harvard.edu}}</ref>. For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]]<ref name=":2" />, i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.		Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible)<ref>{{Cite web \|title=6.046J Lecture 22: Derandomization {{!}} Design and Analysis of Algorithms {{!}} Electrical Engineering and Computer Science \|url=https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/ \|access-date=2024-12-27 \|website=MIT OpenCourseWare \|language=en}}</ref><ref>{{Cite report \|url=https://dl.acm.org/doi/10.5555/894682 \|title=Pairwise Independence and Derandomization \|last1=Luby \|first1=Michael \|last2=Wigderson \|first2=Avi \|date=July 1995 \|publisher=University of California at Berkeley \|location=USA}}</ref>. It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time<ref name=":2">{{Cite web \|title=Lecture Notes, Chapter 3. Basic Derandomization Techniques \|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm \|access-date=2024-12-27 \|website=people.seas.harvard.edu}}</ref>. For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]]<ref name=":2" />, i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.

	There are specific methods that can be employed to derandomize particular randomized algorithms:		There are specific methods that can be employed to derandomize particular randomized algorithms:

User-duck: Cite CE.

2024-12-27T18:46:48Z

Cite CE.

Eannaj: /* Derandomization */ I added references to the derandomization section.

2024-12-27T17:51:18Z

Derandomization: I added references to the derandomization section.

← Previous revision		Revision as of 17:51, 27 December 2024
Line 159:		Line 159:
	{{Unreferenced\|section\|date=September 2023}}		{{Unreferenced\|section\|date=September 2023}}

	Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible). It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time. For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]], i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.		Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible)<ref>{{Cite web \|title=6.046J Lecture 22: Derandomization {{!}} Design and Analysis of Algorithms {{!}} Electrical Engineering and Computer Science \|url=https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/ \|access-date=2024-12-27 \|website=MIT OpenCourseWare \|language=en}}</ref><ref>{{Cite report \|url=https://dl.acm.org/doi/10.5555/894682 \|title=Pairwise Independence and Derandomization \|last=Luby \|first=Michael \|last2=Wigderson \|first2=Avi \|date=1995-06 \|publisher=University of California at Berkeley \|doi=10.5555/894682 \|location=USA}}</ref>. It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time<ref name=":2">{{Cite web \|title=Lecture Notes, Chapter 3. Basic Derandomization Techniques, \|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm \|access-date=2024-12-27 \|website=people.seas.harvard.edu}}</ref>. For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]]<ref name=":2" />, i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.

	There are specific methods that can be employed to derandomize particular randomized algorithms:		There are specific methods that can be employed to derandomize particular randomized algorithms:

AlgorithmSoup at 15:24, 27 December 2024

2024-12-27T15:24:11Z

← Previous revision		Revision as of 15:24, 27 December 2024
Line 81:		Line 81:

	=== Implicit uses in combinatorics ===		=== Implicit uses in combinatorics ===
	Prior to the popularization of randomized algorithms in computer science, [[Paul Erdős]] popularized the use of randomized constructions as a mathematical technique for establishing the existence of mathematical objects. This technique has become known as the [[probabilistic method]].<ref name=":1">{{Cite book \|last=Alon \|first=Noga \|url=https://www.worldcat.org/oclc/910535517 \|title=The probabilistic method \|date=2016 \|others=Joel H. Spencer \|isbn=978-1-119-06195-3 \|edition=Fourth \|location=Hoboken, New Jersey \|oclc=910535517}}</ref> [[Paul Erdős\|Erdős]] gave his first application of the probabilistic method in 1947, when he used a simple randomized construction to establish the existence of Ramsey graphs.<ref>P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. '''53''' (1947), 292--294 '''MR'''8,479d; '''Zentralblatt''' 32,192.</ref> He famously used a ~~much~~ more sophisticated randomized algorithm in 1959 to establish the existence of graphs with high girth and chromatic number.<ref>{{Cite journal \|last=Erdös \|first=P. \|date=1959 \|title=Graph Theory and Probability \|journal=Canadian Journal of Mathematics \|language=en \|volume=11 \|pages=34–38 \|doi=10.4153/CJM-1959-003-9 \|s2cid=122784453 \|issn=0008-414X\|doi-access=free }}</ref><ref name=":1" />		Prior to the popularization of randomized algorithms in computer science, [[Paul Erdős]] popularized the use of randomized constructions as a mathematical technique for establishing the existence of mathematical objects. This technique has become known as the [[probabilistic method]].<ref name=":1">{{Cite book \|last=Alon \|first=Noga \|url=https://www.worldcat.org/oclc/910535517 \|title=The probabilistic method \|date=2016 \|others=Joel H. Spencer \|isbn=978-1-119-06195-3 \|edition=Fourth \|location=Hoboken, New Jersey \|oclc=910535517}}</ref> [[Paul Erdős\|Erdős]] gave his first application of the probabilistic method in 1947, when he used a simple randomized construction to establish the existence of Ramsey graphs.<ref>P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. '''53''' (1947), 292--294 '''MR'''8,479d; '''Zentralblatt''' 32,192.</ref> He famously used a more sophisticated randomized algorithm in 1959 to establish the existence of graphs with high girth and chromatic number.<ref>{{Cite journal \|last=Erdös \|first=P. \|date=1959 \|title=Graph Theory and Probability \|journal=Canadian Journal of Mathematics \|language=en \|volume=11 \|pages=34–38 \|doi=10.4153/CJM-1959-003-9 \|s2cid=122784453 \|issn=0008-414X\|doi-access=free }}</ref><ref name=":1" />

	==Examples==		==Examples==

Skyerise: /* See also */ sort

2024-03-30T21:10:48Z

Skyerise: copyedit

2024-03-30T21:09:31Z

copyedit

← Previous revision		Revision as of 21:09, 30 March 2024
Line 4:		Line 4:
	A '''randomized algorithm''' is an [[algorithm]] that employs a degree of [[randomness]] as part of its logic or procedure. The algorithm typically uses [[Uniform distribution (discrete)\|uniformly random]] bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.		A '''randomized algorithm''' is an [[algorithm]] that employs a degree of [[randomness]] as part of its logic or procedure. The algorithm typically uses [[Uniform distribution (discrete)\|uniformly random]] bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.

	~~One~~ ~~has~~ to ~~distinguish~~ between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite ([[Las Vegas algorithm]]s, for example [[Quicksort]]<ref>{{Cite journal\|last=Hoare\|first=C. A. R.\|date=July 1961\|title=Algorithm 64: Quicksort\|journal=Commun. ACM\|volume=4\|issue=7\|pages=321–\|doi=10.1145/366622.366644\|issn=0001-0782}}</ref>), and algorithms which have a chance of producing an incorrect result ([[Monte Carlo algorithm]]s, for example the Monte Carlo algorithm for the [[Minimum feedback arc set\|MFAS]] problem<ref>{{Cite journal\|last=Kudelić\|first=Robert\|date=2016-04-01\|title=Monte-Carlo randomized algorithm for minimal feedback arc set problem\|journal=Applied Soft Computing\|volume=41\|pages=235–246\|doi=10.1016/j.asoc.2015.12.018}}</ref>) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem.<ref>"In [[primality test\|testing primality]] of very large numbers chosen at random, the chance of stumbling upon a value that fools the [[Fermat primality test\|Fermat test]] is less than the chance that [[cosmic radiation]] will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." [[Hal Abelson]] and [[Gerald J. Sussman]] (1996). ''[[Structure and Interpretation of Computer Programs]]''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2].</ref>		There is a distinction between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite ([[Las Vegas algorithm]]s, for example [[Quicksort]]<ref>{{Cite journal\|last=Hoare\|first=C. A. R.\|date=July 1961\|title=Algorithm 64: Quicksort\|journal=Commun. ACM\|volume=4\|issue=7\|pages=321–\|doi=10.1145/366622.366644\|issn=0001-0782}}</ref>), and algorithms which have a chance of producing an incorrect result ([[Monte Carlo algorithm]]s, for example the Monte Carlo algorithm for the [[Minimum feedback arc set\|MFAS]] problem<ref>{{Cite journal\|last=Kudelić\|first=Robert\|date=2016-04-01\|title=Monte-Carlo randomized algorithm for minimal feedback arc set problem\|journal=Applied Soft Computing\|volume=41\|pages=235–246\|doi=10.1016/j.asoc.2015.12.018}}</ref>) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem.<ref>"In [[primality test\|testing primality]] of very large numbers chosen at random, the chance of stumbling upon a value that fools the [[Fermat primality test\|Fermat test]] is less than the chance that [[cosmic radiation]] will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." [[Hal Abelson]] and [[Gerald J. Sussman]] (1996). ''[[Structure and Interpretation of Computer Programs]]''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2].</ref>

	In common practice, randomized algorithms are approximated using a [[pseudorandom number generator]] in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior and mathematical guarantees which may depend on the existence of an ideal true random number generator.		In common practice, randomized algorithms are approximated using a [[pseudorandom number generator]] in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior and mathematical guarantees which may depend on the existence of an ideal true random number generator.

Citation bot: Added isbn. Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Superegz | Category:Vague or ambiguous time from September 2023‎ | #UCB_Category 311/353

2024-03-09T08:43:12Z

Added isbn. Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Superegz | Category:Vague or ambiguous time from September 2023‎ | #UCB_Category 311/353

← Previous revision		Revision as of 08:43, 9 March 2024
Line 70:		Line 70:

	=== Number theory ===		=== Number theory ===
	In 1917, [[Henry Cabourn Pocklington]] introduced a randomized algorithm known as [[Pocklington's algorithm]] for efficiently finding [[square root]]s modulo prime numbers.<ref>{{citation \|last1=Williams \|first1=H. C. \|title=Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993 \|volume=48 \|pages=481–531 \|year=1994 \|editor-last=Gautschi \|editor-first=Walter \|series=Proceedings of Symposia in Applied Mathematics \|contribution=Factoring integers before computers \|publisher=Amer. Math. Soc., Providence, RI \|doi=10.1090/psapm/048/1314885 \|mr=1314885 \|last2=Shallit \|first2=J. O. \|author1-link=Hugh C. Williams \|author2-link=Jeffrey Shallit}}; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".</ref>		In 1917, [[Henry Cabourn Pocklington]] introduced a randomized algorithm known as [[Pocklington's algorithm]] for efficiently finding [[square root]]s modulo prime numbers.<ref>{{citation \|last1=Williams \|first1=H. C. \|title=Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993 \|volume=48 \|pages=481–531 \|year=1994 \|editor-last=Gautschi \|editor-first=Walter \|series=Proceedings of Symposia in Applied Mathematics \|contribution=Factoring integers before computers \|publisher=Amer. Math. Soc., Providence, RI \|doi=10.1090/psapm/048/1314885 \|mr=1314885 \|last2=Shallit \|first2=J. O. \|isbn=978-0-8218-0291-5 \|author1-link=Hugh C. Williams \|author2-link=Jeffrey Shallit}}; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".</ref>
	In 1970, [[Elwyn Berlekamp]] introduced a randomized algorithm for efficiently computing the roots of a polynomial over a finite field.<ref>{{Cite book \|last=Berlekamp \|first=E. R. \|title=Proceedings of the second ACM symposium on Symbolic and algebraic manipulation - SYMSAC '71 \|chapter=Factoring polynomials over large finite fields \|date=1971 \|chapter-url=http://portal.acm.org/citation.cfm?doid=800204.806290 \|language=en \|location=Los Angeles, California, United States \|publisher=ACM Press \|pages=223 \|doi=10.1145/800204.806290\|isbn=9781450377867 \|s2cid=6464612 }}</ref> In 1977, [[Robert M. Solovay]] and [[Volker Strassen]] discovered a polynomial-time [[Solovay–Strassen primality test\|randomized primality test]] (i.e., determining the [[primality test\|primality]] of a number). Soon afterwards [[Michael O. Rabin]] demonstrated that the 1976 [[Miller–Rabin primality test\|Miller's primality test]] could also be turned into a polynomial-time randomized algorithm. At that time, no provably polynomial-time [[deterministic algorithm\|deterministic algorithms]] for primality testing were known.		In 1970, [[Elwyn Berlekamp]] introduced a randomized algorithm for efficiently computing the roots of a polynomial over a finite field.<ref>{{Cite book \|last=Berlekamp \|first=E. R. \|title=Proceedings of the second ACM symposium on Symbolic and algebraic manipulation - SYMSAC '71 \|chapter=Factoring polynomials over large finite fields \|date=1971 \|chapter-url=http://portal.acm.org/citation.cfm?doid=800204.806290 \|language=en \|location=Los Angeles, California, United States \|publisher=ACM Press \|pages=223 \|doi=10.1145/800204.806290\|isbn=9781450377867 \|s2cid=6464612 }}</ref> In 1977, [[Robert M. Solovay]] and [[Volker Strassen]] discovered a polynomial-time [[Solovay–Strassen primality test\|randomized primality test]] (i.e., determining the [[primality test\|primality]] of a number). Soon afterwards [[Michael O. Rabin]] demonstrated that the 1976 [[Miller–Rabin primality test\|Miller's primality test]] could also be turned into a polynomial-time randomized algorithm. At that time, no provably polynomial-time [[deterministic algorithm\|deterministic algorithms]] for primality testing were known.

Line 78:		Line 78:
	Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.<ref name=":0" /> In 1979, Carter and Wegman introduced [[Universal hashing\|universal hash functions]],<ref>{{Cite journal \|last1=Carter \|first1=J. Lawrence \|last2=Wegman \|first2=Mark N. \|date=1979-04-01 \|title=Universal classes of hash functions \|journal=Journal of Computer and System Sciences \|language=en \|volume=18 \|issue=2 \|pages=143–154 \|doi=10.1016/0022-0000(79)90044-8 \|issn=0022-0000\|doi-access=free }}</ref> which they showed could be used to implement chained hash tables with constant expected time per operation.		Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.<ref name=":0" /> In 1979, Carter and Wegman introduced [[Universal hashing\|universal hash functions]],<ref>{{Cite journal \|last1=Carter \|first1=J. Lawrence \|last2=Wegman \|first2=Mark N. \|date=1979-04-01 \|title=Universal classes of hash functions \|journal=Journal of Computer and System Sciences \|language=en \|volume=18 \|issue=2 \|pages=143–154 \|doi=10.1016/0022-0000(79)90044-8 \|issn=0022-0000\|doi-access=free }}</ref> which they showed could be used to implement chained hash tables with constant expected time per operation.

	Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as the [[Bloom filter]].<ref>{{Cite journal \|last=Bloom \|first=Burton H. \|date=July 1970 \|title=Space/time trade-offs in hash coding with allowable errors ~~\|url=http://dx.doi.org/10.1145/362686.362692~~ \|journal=Communications of the ACM \|volume=13 \|issue=7 \|pages=422–426 \|doi=10.1145/362686.362692 \|s2cid=7931252 \|issn=0001-0782\|doi-access=free }}</ref> In 1989, [[Raimund Seidel]] and [[Cecilia R. Aragon]] introduced a randomized balanced search tree known as the [[treap]].<ref>{{Cite book \|last1=Aragon \|first1=C.R. \|last2=Seidel \|first2=R.G. \|title=30th Annual Symposium on Foundations of Computer Science \|chapter=Randomized search trees \|date=October 1989 \|chapter-url=https://ieeexplore.ieee.org/document/63531 \|pages=540–545 \|doi=10.1109/SFCS.1989.63531\|isbn=0-8186-1982-1 }}</ref> In the same year, [[William Pugh (computer scientist)\|William Pugh]] introduced another randomized search tree known as the [[skip list]].<ref>[[William Pugh (computer scientist)\|Pugh, William]] (April 1989). ''[http://drum.lib.umd.edu/handle/1903/542 Concurrent Maintenance of Skip Lists]'' (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.</ref>		Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as the [[Bloom filter]].<ref>{{Cite journal \|last=Bloom \|first=Burton H. \|date=July 1970 \|title=Space/time trade-offs in hash coding with allowable errors \|journal=Communications of the ACM \|volume=13 \|issue=7 \|pages=422–426 \|doi=10.1145/362686.362692 \|s2cid=7931252 \|issn=0001-0782\|doi-access=free }}</ref> In 1989, [[Raimund Seidel]] and [[Cecilia R. Aragon]] introduced a randomized balanced search tree known as the [[treap]].<ref>{{Cite book \|last1=Aragon \|first1=C.R. \|last2=Seidel \|first2=R.G. \|title=30th Annual Symposium on Foundations of Computer Science \|chapter=Randomized search trees \|date=October 1989 \|chapter-url=https://ieeexplore.ieee.org/document/63531 \|pages=540–545 \|doi=10.1109/SFCS.1989.63531\|isbn=0-8186-1982-1 }}</ref> In the same year, [[William Pugh (computer scientist)\|William Pugh]] introduced another randomized search tree known as the [[skip list]].<ref>[[William Pugh (computer scientist)\|Pugh, William]] (April 1989). ''[http://drum.lib.umd.edu/handle/1903/542 Concurrent Maintenance of Skip Lists]'' (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.</ref>

	=== Implicit uses in combinatorics ===		=== Implicit uses in combinatorics ===
Line 191:		Line 191:
	\| series = Natural Computing Series		\| series = Natural Computing Series
	\| title = Algorithmic Bioprocesses		\| title = Algorithmic Bioprocesses
	\| year = 2009\| url = https://authors.library.caltech.edu/26121/1/etr090.pdf }}.</ref>		\| year = 2009\| isbn = 978-3-540-88868-0 \| url = https://authors.library.caltech.edu/26121/1/etr090.pdf }}.</ref>

	==See also==		==See also==

Jarble: adding Template:Algorithms and data structures

2024-02-02T20:06:51Z

adding Template:Algorithms and data structures

← Previous revision		Revision as of 20:06, 2 February 2024
Line 224:		Line 224:

	{{DEFAULTSORT:Randomized Algorithm}}		{{DEFAULTSORT:Randomized Algorithm}}
			{{Algorithms and data structures}}
	[[Category:Randomized algorithms\| ]]		[[Category:Randomized algorithms\| ]]
	[[Category:Analysis of algorithms]]		[[Category:Analysis of algorithms]]

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

2023-11-27T15:30:11Z

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

← Previous revision		Revision as of 15:30, 27 November 2023
Line 78:		Line 78:
	Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.<ref name=":0" /> In 1979, Carter and Wegman introduced [[Universal hashing\|universal hash functions]],<ref>{{Cite journal \|last1=Carter \|first1=J. Lawrence \|last2=Wegman \|first2=Mark N. \|date=1979-04-01 \|title=Universal classes of hash functions \|journal=Journal of Computer and System Sciences \|language=en \|volume=18 \|issue=2 \|pages=143–154 \|doi=10.1016/0022-0000(79)90044-8 \|issn=0022-0000\|doi-access=free }}</ref> which they showed could be used to implement chained hash tables with constant expected time per operation.		Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.<ref name=":0" /> In 1979, Carter and Wegman introduced [[Universal hashing\|universal hash functions]],<ref>{{Cite journal \|last1=Carter \|first1=J. Lawrence \|last2=Wegman \|first2=Mark N. \|date=1979-04-01 \|title=Universal classes of hash functions \|journal=Journal of Computer and System Sciences \|language=en \|volume=18 \|issue=2 \|pages=143–154 \|doi=10.1016/0022-0000(79)90044-8 \|issn=0022-0000\|doi-access=free }}</ref> which they showed could be used to implement chained hash tables with constant expected time per operation.

	Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as the [[Bloom filter]].<ref>{{Cite journal \|last=Bloom \|first=Burton H. \|date=July 1970 \|title=Space/time trade-offs in hash coding with allowable errors \|url=http://dx.doi.org/10.1145/362686.362692 \|journal=Communications of the ACM \|volume=13 \|issue=7 \|pages=422–426 \|doi=10.1145/362686.362692 \|s2cid=7931252 \|issn=0001-0782}}</ref> In 1989, [[Raimund Seidel]] and [[Cecilia R. Aragon]] introduced a randomized balanced search tree known as the [[treap]].<ref>{{Cite book \|last1=Aragon \|first1=C.R. \|last2=Seidel \|first2=R.G. \|title=30th Annual Symposium on Foundations of Computer Science \|chapter=Randomized search trees \|date=October 1989 \|chapter-url=https://ieeexplore.ieee.org/document/63531 \|pages=540–545 \|doi=10.1109/SFCS.1989.63531\|isbn=0-8186-1982-1 }}</ref> In the same year, [[William Pugh (computer scientist)\|William Pugh]] introduced another randomized search tree known as the [[skip list]].<ref>[[William Pugh (computer scientist)\|Pugh, William]] (April 1989). ''[http://drum.lib.umd.edu/handle/1903/542 Concurrent Maintenance of Skip Lists]'' (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.</ref>		Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as the [[Bloom filter]].<ref>{{Cite journal \|last=Bloom \|first=Burton H. \|date=July 1970 \|title=Space/time trade-offs in hash coding with allowable errors \|url=http://dx.doi.org/10.1145/362686.362692 \|journal=Communications of the ACM \|volume=13 \|issue=7 \|pages=422–426 \|doi=10.1145/362686.362692 \|s2cid=7931252 \|issn=0001-0782\|doi-access=free }}</ref> In 1989, [[Raimund Seidel]] and [[Cecilia R. Aragon]] introduced a randomized balanced search tree known as the [[treap]].<ref>{{Cite book \|last1=Aragon \|first1=C.R. \|last2=Seidel \|first2=R.G. \|title=30th Annual Symposium on Foundations of Computer Science \|chapter=Randomized search trees \|date=October 1989 \|chapter-url=https://ieeexplore.ieee.org/document/63531 \|pages=540–545 \|doi=10.1109/SFCS.1989.63531\|isbn=0-8186-1982-1 }}</ref> In the same year, [[William Pugh (computer scientist)\|William Pugh]] introduced another randomized search tree known as the [[skip list]].<ref>[[William Pugh (computer scientist)\|Pugh, William]] (April 1989). ''[http://drum.lib.umd.edu/handle/1903/542 Concurrent Maintenance of Skip Lists]'' (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.</ref>

	=== Implicit uses in combinatorics ===		=== Implicit uses in combinatorics ===

← Previous revision		Revision as of 21:10, 30 March 2024
Line 194:		Line 194:

	==See also==		==See also==
		⚫	*[[Approximate counting algorithm]]
⚫	*[[Probabilistic analysis of algorithms]]
	*[[Atlantic City algorithm]]		*[[Atlantic City algorithm]]
⚫	*[[Monte Carlo algorithm]]
⚫	*[[Las Vegas algorithm]]
	*[[Bogosort]]		*[[Bogosort]]
		⚫	*[[Count–min sketch]]
⚫	*[[Principle of deferred decision]]
⚫	*[[Randomized algorithms as zero-sum games]]
⚫	*[[Probabilistic roadmap]]
	*[[HyperLogLog]]		*[[HyperLogLog]]
⚫	*[[~~count–min~~ sketch]]
⚫	*[[~~approximate~~ counting algorithm]]
	*[[Karger's algorithm]]		*[[Karger's algorithm]]
		⚫	*[[Las Vegas algorithm]]
		⚫	*[[Monte Carlo algorithm]]
		⚫	*[[Principle of deferred decision]]
		⚫	*[[Probabilistic analysis of algorithms]]
		⚫	*[[Probabilistic roadmap]]
		⚫	*[[Randomized algorithms as zero-sum games]]

	==Notes==		==Notes==

← Previous revision		Revision as of 18:46, 27 December 2024
Line 81:		Line 81:

	=== Implicit uses in combinatorics ===		=== Implicit uses in combinatorics ===
	Prior to the popularization of randomized algorithms in computer science, [[Paul Erdős]] popularized the use of randomized constructions as a mathematical technique for establishing the existence of mathematical objects. This technique has become known as the [[probabilistic method]].<ref name=":1">{{Cite book \|last=Alon \|first=Noga ~~\|url=https://www.worldcat.org/oclc/910535517~~ \|title=The probabilistic method \|date=2016 \|~~others~~=Joel H. Spencer \|isbn=978-1-119-06195-3 \|edition=Fourth \|location=Hoboken, New Jersey \|oclc=910535517}}</ref> [[Paul Erdős\|Erdős]] gave his first application of the probabilistic method in 1947, when he used a simple randomized construction to establish the existence of Ramsey graphs.<ref>P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. '''53''' (1947), 292--294 '''MR'''8,479d; '''Zentralblatt''' 32,192.</ref> He famously used a more sophisticated randomized algorithm in 1959 to establish the existence of graphs with high girth and chromatic number.<ref>{{Cite journal \|last=Erdös \|first=P. \|date=1959 \|title=Graph Theory and Probability \|journal=Canadian Journal of Mathematics \|language=en \|volume=11 \|pages=34–38 \|doi=10.4153/CJM-1959-003-9 \|s2cid=122784453 \|issn=0008-414X\|doi-access=free }}</ref><ref name=":1" />		Prior to the popularization of randomized algorithms in computer science, [[Paul Erdős]] popularized the use of randomized constructions as a mathematical technique for establishing the existence of mathematical objects. This technique has become known as the [[probabilistic method]].<ref name=":1">{{Cite book \|last=Alon \|first=Noga \|title=The probabilistic method \|date=2016 \|first2=Joel H. \|last2=Spencer \|isbn=978-1-119-06195-3 \|edition=Fourth \|publisher=Wiley \|location=Hoboken, New Jersey \|oclc=910535517}}</ref> [[Paul Erdős\|Erdős]] gave his first application of the probabilistic method in 1947, when he used a simple randomized construction to establish the existence of Ramsey graphs.<ref>P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. '''53''' (1947), 292--294 '''MR'''8,479d; '''Zentralblatt''' 32,192.</ref> He famously used a more sophisticated randomized algorithm in 1959 to establish the existence of graphs with high girth and chromatic number.<ref>{{Cite journal \|last=Erdös \|first=P. \|date=1959 \|title=Graph Theory and Probability \|journal=Canadian Journal of Mathematics \|language=en \|volume=11 \|pages=34–38 \|doi=10.4153/CJM-1959-003-9 \|s2cid=122784453 \|issn=0008-414X\|doi-access=free }}</ref><ref name=":1" />

	==Examples==		==Examples==
Line 159:		Line 159:
	{{Unreferenced\|section\|date=September 2023}}		{{Unreferenced\|section\|date=September 2023}}

	Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible)<ref>{{Cite web \|title=6.046J Lecture 22: Derandomization {{!}} Design and Analysis of Algorithms {{!}} Electrical Engineering and Computer Science \|url=https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/ \|access-date=2024-12-27 \|website=MIT OpenCourseWare \|language=en}}</ref><ref>{{Cite report \|url=https://dl.acm.org/doi/10.5555/894682 \|title=Pairwise Independence and Derandomization \|last=Luby \|first=Michael \|last2=Wigderson \|first2=Avi \|date=1995~~-06~~ \|publisher=University of California at Berkeley \|doi=10.5555/894682 \|location=USA}}</ref>. It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time<ref name=":2">{{Cite web \|title=Lecture Notes, Chapter 3. Basic Derandomization Techniques, \|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm \|access-date=2024-12-27 \|website=people.seas.harvard.edu}}</ref>. For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]]<ref name=":2" />, i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.		Randomness can be viewed as a resource, like space and time. Derandomization is then the process of ''removing'' randomness (or using as little of it as possible)<ref>{{Cite web \|title=6.046J Lecture 22: Derandomization {{!}} Design and Analysis of Algorithms {{!}} Electrical Engineering and Computer Science \|url=https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/resources/mit6_046js12_lec22/ \|access-date=2024-12-27 \|website=MIT OpenCourseWare \|language=en}}</ref><ref>{{Cite report \|url=https://dl.acm.org/doi/10.5555/894682 \|title=Pairwise Independence and Derandomization \|last=Luby \|first=Michael \|last2=Wigderson \|first2=Avi \|date=July 1995 \|publisher=University of California at Berkeley \|doi=10.5555/894682 \|location=USA}}</ref>. It is not currently known{{As of?\|date=September 2023}} if all algorithms can be derandomized without significantly increasing their running time<ref name=":2">{{Cite web \|title=Lecture Notes, Chapter 3. Basic Derandomization Techniques, \|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm \|access-date=2024-12-27 \|website=people.seas.harvard.edu}}</ref>. For instance, in [[analysis of algorithms\|computational complexity]], it is unknown whether [[P (complexity)\|P]] = [[Bounded-error probabilistic polynomial\|BPP]]<ref name=":2" />, i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.

	There are specific methods that can be employed to derandomize particular randomized algorithms:		There are specific methods that can be employed to derandomize particular randomized algorithms:
Line 173:		Line 173:
	* The natural way of carrying out a numerical computation in [[embedded systems]] or [[cyber-physical system]]s is to provide a result that approximates the correct one with high probability (or Probably Approximately Correct Computation (PACC)). The hard problem associated with the evaluation of the discrepancy loss between the approximated and the correct computation can be effectively addressed by resorting to randomization<ref>{{citation\|title=Intelligence for Embedded Systems\|first1=Cesare\|last1=Alippi\|publisher=Springer\|year=2014\|isbn=978-3-319-05278-6}}.</ref>		* The natural way of carrying out a numerical computation in [[embedded systems]] or [[cyber-physical system]]s is to provide a result that approximates the correct one with high probability (or Probably Approximately Correct Computation (PACC)). The hard problem associated with the evaluation of the discrepancy loss between the approximated and the correct computation can be effectively addressed by resorting to randomization<ref>{{citation\|title=Intelligence for Embedded Systems\|first1=Cesare\|last1=Alippi\|publisher=Springer\|year=2014\|isbn=978-3-319-05278-6}}.</ref>
	* In [[communication complexity]], the equality of two strings can be verified to some reliability using <math>\log n</math> bits of communication with a randomized protocol. Any deterministic protocol requires <math>\Theta(n)</math> bits if defending against a strong opponent.<ref>{{citation\|title=Communication Complexity\|first1=Eyal\|last1=Kushilevitz\|first2=Noam\|last2=Nisan\|publisher=Cambridge University Press\|year=2006\|isbn=9780521029834}}. For the deterministic lower bound see p. 11; for the logarithmic randomized upper bound see pp. 31–32.</ref>		* In [[communication complexity]], the equality of two strings can be verified to some reliability using <math>\log n</math> bits of communication with a randomized protocol. Any deterministic protocol requires <math>\Theta(n)</math> bits if defending against a strong opponent.<ref>{{citation\|title=Communication Complexity\|first1=Eyal\|last1=Kushilevitz\|first2=Noam\|last2=Nisan\|publisher=Cambridge University Press\|year=2006\|isbn=9780521029834}}. For the deterministic lower bound see p. 11; for the logarithmic randomized upper bound see pp. 31–32.</ref>
	* The volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time.<ref>{{citation\|last1=Dyer\|first1=M.\|last2=Frieze\|first2=A.\|last3=Kannan\|first3=R.\|title=A random polynomial-time algorithm for approximating the volume of convex bodies\|journal=[[Journal of the ACM]]\|volume=38\|issue=1\|year=1991\|pages=1–17\|doi=10.1145/102782.102783\|s2cid=13268711\|url=http://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf}}</ref> [[Imre Bárány\|Bárány]] and [[Zoltán Füredi\|Füredi]] showed that no deterministic algorithm can do the same.<ref>{{citation\|last1=Füredi\|first1=Z.\|author1-link=Zoltán Füredi\|last2=Bárány\|first2=I.\|year=1986\|contribution=Computing the volume is difficult\|title=Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986)\|publisher=ACM\|location=New York, NY\|pages=442–447\|doi=10.1145/12130.12176\|citeseerx=10.1.1.726.9448\|isbn=0-89791-193-8 \|s2cid=17867291\|url=https://ecommons.cornell.edu/bitstream/1813/8572/1/TR000688.pdf}}</ref> This is true unconditionally, i.e. without relying on any complexity-theoretic assumptions, assuming the convex body can be queried only as a black box.		* The volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time.<ref>{{citation \|last1=Dyer \|first1=M. \|last2=Frieze \|first2=A. \|last3=Kannan \|first3=R. \|title=A random polynomial-time algorithm for approximating the volume of convex bodies \|journal=[[Journal of the ACM]] \|volume=38 \|issue=1 \|year=1991 \|pages=1–17 \|doi=10.1145/102782.102783 \|s2cid=13268711 \|url=http://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf}}</ref> [[Imre Bárány\|Bárány]] and [[Zoltán Füredi\|Füredi]] showed that no deterministic algorithm can do the same.<ref>{{citation \|last1=Füredi \|first1=Z. \|author1-link=Zoltán Füredi \|last2=Bárány \|first2=I. \|year=1986 \|contribution=Computing the volume is difficult \|title=Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986) \|publisher=ACM \|location=New York, NY \|pages=442–447 \|doi=10.1145/12130.12176 \|citeseerx=10.1.1.726.9448 \|isbn=0-89791-193-8 \|s2cid=17867291 \|url=https://ecommons.cornell.edu/bitstream/1813/8572/1/TR000688.pdf}}</ref> This is true unconditionally, i.e. without relying on any complexity-theoretic assumptions, assuming the convex body can be queried only as a black box.
	* A more complexity-theoretic example of a place where randomness appears to help is the class [[IP (complexity)\|IP]]. IP consists of all languages that can be accepted (with high probability) by a polynomially long interaction between an all-powerful prover and a verifier that implements a BPP algorithm. IP = [[PSPACE]].<ref>{{citation\|last=Shamir\|first=A.\|author-link=Adi Shamir\|title=IP = PSPACE\|journal=Journal of the ACM\|volume=39\|issue=4\|year=1992\|pages=869–877\|doi=10.1145/146585.146609\|s2cid=315182\|doi-access=free}}</ref> However, if it is required that the verifier be deterministic, then IP = [[NP (complexity)\|NP]].		* A more complexity-theoretic example of a place where randomness appears to help is the class [[IP (complexity)\|IP]]. IP consists of all languages that can be accepted (with high probability) by a polynomially long interaction between an all-powerful prover and a verifier that implements a BPP algorithm. IP = [[PSPACE]].<ref>{{citation \|last=Shamir \|first=A. \|author-link=Adi Shamir \|title=IP = PSPACE \|journal=Journal of the ACM \|volume=39 \|issue=4 \|year=1992 \|pages=869–877 \|doi=10.1145/146585.146609 \|s2cid=315182 \|doi-access=free}}</ref> However, if it is required that the verifier be deterministic, then IP = [[NP (complexity)\|NP]].
	* In a [[chemical reaction network]] (a finite set of reactions like A+B → 2C + D operating on a finite number of molecules), the ability to ever reach a given target state from an initial state is decidable, while even approximating the probability of ever reaching a given target state (using the standard concentration-based probability for which reaction will occur next) is undecidable. More specifically, a limited Turing machine <!-- the Turing machine has infinite tape --> can be simulated with arbitrarily high probability of running correctly for all time, only if a random chemical reaction network is used. With a simple nondeterministic chemical reaction network (any possible reaction can happen next), the computational power is limited to [[Primitive recursive\|primitive recursive functions]].<ref>{{citation		* In a [[chemical reaction network]] (a finite set of reactions like A+B → 2C + D operating on a finite number of molecules), the ability to ever reach a given target state from an initial state is decidable, while even approximating the probability of ever reaching a given target state (using the standard concentration-based probability for which reaction will occur next) is undecidable. More specifically, a limited Turing machine <!-- the Turing machine has infinite tape --> can be simulated with arbitrarily high probability of running correctly for all time, only if a random chemical reaction network is used. With a simple nondeterministic chemical reaction network (any possible reaction can happen next), the computational power is limited to [[Primitive recursive\|primitive recursive functions]].<ref>{{citation
	\| last1 = Cook \| first1 = Matthew \| author1-link = Matthew Cook		\| last1 = Cook \| first1 = Matthew \| author1-link = Matthew Cook
	\| last2 = Soloveichik \| first2 = David		\| last2 = Soloveichik \| first2 = David