Rational Point: sp

2025-02-26T08:42:59Z

← Older revision		Revision as of 08:42, 26 February 2025
Line 10:		Line 10:
	An algorithm with one-sided error may be combined with an algorithm having one-sided complementary error to yield a Las Vegas type algorithm with zero-sided error.		An algorithm with one-sided error may be combined with an algorithm having one-sided complementary error to yield a Las Vegas type algorithm with zero-sided error.

	A Las Vegas algorithm always produces the correct result when and if it terminates, but termination is not guaranteed except in the ~~probabalistic~~ sense of a finite expected running time.		A Las Vegas algorithm always produces the correct result when and if it terminates, but termination is not guaranteed except in the probabilistic sense of a finite expected running time.

	Algorithms with one-sided error are subject to “Type I” errors only, but the probability of error is bounded away from one.		Algorithms with one-sided error are subject to “Type I” errors only, but the probability of error is bounded away from one.

Rational Point: basic defs, refs

2025-02-26T01:35:51Z

basic defs, refs

New page

A '''randomized algorithm''' is generally classified by its '''error''' as one of four types:

* zero-sided;
* one-sided;
* one-sided complementary; or
* two-sided.

A randomized algorithm with zero-sided error is said to be of Las Vegas type, whereas it is of Monte Carlo type if it has a two-sided error.

An algorithm with one-sided error may be combined with an algorithm having one-sided complementary error to yield a Las Vegas type algorithm with zero-sided error.

A Las Vegas algorithm always produces the correct result when and if it terminates, but termination is not guaranteed except in the probabalistic sense of a finite expected running time.

Algorithms with one-sided error are subject to “Type I” errors only, but the probability of error is bounded away from one.

Algorithms with one-sided complementary error are subject to “Type II” errors only, and likewise the probability of error is bounded away from one.

Algorithms with two-sided error are subject to both “Type I” and “Type II” errors <ref>https://www.simplypsychology.org/type_i_and_type_ii_errors.html</ref>, but the conditional probabilities of “Type I” and “Type II” errors are strictly less than one half and bounded away from one half.

An algorithm with one-sided, one-sided complementary, or two-sided error may be run repeatedly until any desired statistical significance of the result is attained.

Complexity classes ''ZPP'', ''RP'', co-''RP'' and ''BPP'' are defined based on the existence of randomized algorithms that run in polynomial time <ref>https://complexityzoo.net/Complexity_Zoo</ref>.

Randomized algorithm - Revision history

Rational Point: sp

Rational Point: basic defs, refs