Randomized algorithm - Revision history

Nubzor: Reverted edits by 2409:40F2:2016:1A91:181D:F5FF:FE51:B916 (talk) (HG) (3.4.13)

2025-06-21T17:33:04Z

Reverted edits by 2409:40F2:2016:1A91:181D:F5FF:FE51:B916 (talk) (HG) (3.4.13)

← Previous revision		Revision as of 17:33, 21 June 2025
Line 6:		Line 6:
	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>		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.~~15818~~		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.
	68594
	61515

	==Motivation==		==Motivation==

2409:40F2:2016:1A91:181D:F5FF:FE51:B916: 15818 68594 61515

2025-06-21T17:32:22Z

15818 68594 61515

← Previous revision		Revision as of 17:32, 21 June 2025
Line 6:		Line 6:
	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>		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.15818
			68594
			61515

	==Motivation==		==Motivation==

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

2025-06-19T20:53:12Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 20:53, 19 June 2025
Line 67:		Line 67:

	=== Sorting ===		=== Sorting ===
	[[Quicksort]] was discovered by [[Tony Hoare]] in 1959, and subsequently published in 1961.<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 64: Quicksort \|url=https://dl.acm.org/doi/10.1145/366622.366644 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321 \|doi=10.1145/366622.366644 \|issn=0001-0782}}</ref> In the same year, Hoare published the [[Quickselect\|quickselect algorithm]],<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 65: find \|url=https://dl.acm.org/doi/10.1145/366622.366647 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321–322 \|doi=10.1145/366622.366647 \|issn=0001-0782}}</ref> which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.<ref>{{Cite journal \|last1=Blum \|first1=Manuel \|last2=Floyd \|first2=Robert W. \|last3=Pratt \|first3=Vaughan \|last4=Rivest \|first4=Ronald L. \|last5=Tarjan \|first5=Robert E. \|date=August 1973 \|title=Time bounds for selection \|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339 \|journal=Journal of Computer and System Sciences \|language=en \|volume=7 \|issue=4 \|pages=448–461 \|doi=10.1016/S0022-0000(73)80033-9}}</ref>		[[Quicksort]] was discovered by [[Tony Hoare]] in 1959, and subsequently published in 1961.<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 64: Quicksort \|url=https://dl.acm.org/doi/10.1145/366622.366644 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321 \|doi=10.1145/366622.366644 \|issn=0001-0782\|url-access=subscription }}</ref> In the same year, Hoare published the [[Quickselect\|quickselect algorithm]],<ref>{{Cite journal \|last=Hoare \|first=C. A. R. \|date=July 1961 \|title=Algorithm 65: find \|url=https://dl.acm.org/doi/10.1145/366622.366647 \|journal=Communications of the ACM \|language=en \|volume=4 \|issue=7 \|pages=321–322 \|doi=10.1145/366622.366647 \|issn=0001-0782\|url-access=subscription }}</ref> which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.<ref>{{Cite journal \|last1=Blum \|first1=Manuel \|last2=Floyd \|first2=Robert W. \|last3=Pratt \|first3=Vaughan \|last4=Rivest \|first4=Ronald L. \|last5=Tarjan \|first5=Robert E. \|date=August 1973 \|title=Time bounds for selection \|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339 \|journal=Journal of Computer and System Sciences \|language=en \|volume=7 \|issue=4 \|pages=448–461 \|doi=10.1016/S0022-0000(73)80033-9}}</ref>

	=== Number theory ===		=== Number theory ===
Line 74:		Line 74:

	=== Data structures ===		=== Data structures ===
	One of the earliest randomized data structures is the [[hash table]], which was introduced in 1953 by [[Hans Peter Luhn]] at [[IBM]].<ref name=":0">{{Cite book \|last=Knuth \|first=Donald E. \|url=https://dl.acm.org/doi/10.5555/280635 \|title=The art of computer programming, volume 3: (2nd ed.) sorting and searching \|date=1998 \|publisher=Addison Wesley Longman Publishing Co., Inc. \|isbn=978-0-201-89685-5 \|location=USA \|pages=536–549 }}</ref> Luhn's hash table used chaining to resolve collisions and was also one of the first applications of [[Linked list\|linked lists]].<ref name=":0" /> Subsequently, in 1954, [[Gene Amdahl]], [[Elaine M. McGraw]], [[Nathaniel Rochester (computer scientist)\|Nathaniel Rochester]], and [[Arthur Samuel (computer scientist)\|Arthur Samuel]] of [[IBM Research]] introduced [[linear probing]],<ref name=":0" /> although [[Andrey Ershov]] independently had the same idea in 1957.<ref name=":0" /> In 1962, [[Donald Knuth]] performed the first correct analysis of linear probing,<ref name=":0" /> although the memorandum containing his analysis was not published until much later.<ref>[[Donald Knuth\|Knuth, Donald]] (1963), ''[https://web.archive.org/web/20160303225949/http://algo.inria.fr/AofA/Research/11-97.html Notes on "Open" Addressing]'', archived from the original on 2016-03-03</ref> The first published analysis was due to Konheim and Weiss in 1966.<ref>{{Cite journal \|last1=Konheim \|first1=Alan G. \|last2=Weiss \|first2=Benjamin \|date=November 1966 \|title=An Occupancy Discipline and Applications \|url=http://dx.doi.org/10.1137/0114101 \|journal=SIAM Journal on Applied Mathematics \|volume=14 \|issue=6 \|pages=1266–1274 \|doi=10.1137/0114101 \|issn=0036-1399}}</ref>		One of the earliest randomized data structures is the [[hash table]], which was introduced in 1953 by [[Hans Peter Luhn]] at [[IBM]].<ref name=":0">{{Cite book \|last=Knuth \|first=Donald E. \|url=https://dl.acm.org/doi/10.5555/280635 \|title=The art of computer programming, volume 3: (2nd ed.) sorting and searching \|date=1998 \|publisher=Addison Wesley Longman Publishing Co., Inc. \|isbn=978-0-201-89685-5 \|location=USA \|pages=536–549 }}</ref> Luhn's hash table used chaining to resolve collisions and was also one of the first applications of [[Linked list\|linked lists]].<ref name=":0" /> Subsequently, in 1954, [[Gene Amdahl]], [[Elaine M. McGraw]], [[Nathaniel Rochester (computer scientist)\|Nathaniel Rochester]], and [[Arthur Samuel (computer scientist)\|Arthur Samuel]] of [[IBM Research]] introduced [[linear probing]],<ref name=":0" /> although [[Andrey Ershov]] independently had the same idea in 1957.<ref name=":0" /> In 1962, [[Donald Knuth]] performed the first correct analysis of linear probing,<ref name=":0" /> although the memorandum containing his analysis was not published until much later.<ref>[[Donald Knuth\|Knuth, Donald]] (1963), ''[https://web.archive.org/web/20160303225949/http://algo.inria.fr/AofA/Research/11-97.html Notes on "Open" Addressing]'', archived from the original on 2016-03-03</ref> The first published analysis was due to Konheim and Weiss in 1966.<ref>{{Cite journal \|last1=Konheim \|first1=Alan G. \|last2=Weiss \|first2=Benjamin \|date=November 1966 \|title=An Occupancy Discipline and Applications \|url=http://dx.doi.org/10.1137/0114101 \|journal=SIAM Journal on Applied Mathematics \|volume=14 \|issue=6 \|pages=1266–1274 \|doi=10.1137/0114101 \|issn=0036-1399\|url-access=subscription }}</ref>

	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.

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.

← 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