Namespaces
Variants
Actions

Difference between revisions of "User:Joachim Draeger/sandbox"

From Encyclopedia of Mathematics
Jump to: navigation, search
Line 1: Line 1:
 +
 +
 +
  
 
{{MSC|68Q05}}
 
{{MSC|68Q05}}
Line 4: Line 7:
 
{{TEX|done}}
 
{{TEX|done}}
  
The universality property of Turing machines states that it exists a Turing machine, which can simulate the behaviour of each other Turing machine. This property is of great practical importance. It says that a Turing machine can be adapted to different tasks by ''programming''; from the viewpoint of computability it is not necessary to build special-purpose machines.
+
A probabilistic Turing machine (PTM) is a [[Turing machine]] (TM) modified for executing a randomized [[Computable function|computation]]. From the computability point of view, a PTM is equivalent to a TM. In other respects, however, the behavior of a PTM is profoundly different from the deterministic computation of a TM; false results, for example, can only be excluded statistically in this model. The physical realization of a true random number generation is possible by performing a measurement process in quantum theory.
 +
 
 +
Some applications of computer science can be better modeled by a PTM than by a classical TM. An example are environments with strong radiation like space missions crossing the radiation belt of Jupiter or robots for handling accidents in a nuclear plant.  But even a usual calculation involving a very large number of single operations (e.g. calculations of $\pi$ with record precision) may be potentially influenced by cosmic rays making the calculation probabilistic.
 +
 
 +
===Definition of a Probabilistic Turing Machine===
 +
 
 +
A PTM $(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ has the same components as a TM. The set $Q$ is a finite set of states, $\Sigma$ is a finite input/output alphabet, $\Gamma$ is a finite tape alphabet with $\Sigma\subseteq\Gamma$, $\sqcup\in \Gamma$ is a blank symbol with $\sqcup \notin \Sigma$, the state $q_0 \in Q$ is a start state, and $q_f \in Q$ is a stop state. The transition function $\delta$, however, does not define deterministic transitions as in the case of a Turing machine, but gives a probability distribution of possible transitions according to $ \delta: Q \times \Sigma \times Q \times \Sigma \times \set{L,R} \longrightarrow [0,1]$.
 +
 
 +
For probabilistic Turing machines, the set $C$ of <i>configurations</i> is defined in the same way as for Turing machines. It is also called the set of <i>basic states</i>. The set $\Omega$ of <i>states</i> is the set of possible probability distributions on the basic states, i.e.  $\Omega=\{(p_c)_{c\in C}\in [0,1]^C\mid \sum_{c\in C} p_c=1\}$.  The set of states serves as memory for the computation history. Since the run of the computation is probabilistic, the definition of a state must be probabilistic as well. Thus the distinction between basic states and states.
 +
 
 +
The transition function $\delta$ can be considered as [[Stochastic matrix|stochastic matrix]] $M_{ji}$ defined on the space $C$ of configurations with $ M_{ji} = \mathrm{Prob}[\delta\colon c_i \mapsto c_j] \in [0,1]$.  As a stochastic matrix, the $L_1$-norm of each column of $M_{ji}$ is equal to 1, i.e. $\sum_i M_{ji} = 1$. $L_1$-norms are preserved by $M$ according to $L_1(M\cdot c) = L_1(c) = \sum_{i} c_i$ for a configuration $c\in C$.  Not every stochastic matrix provides the transition function $\delta$ of a PTM, however, because such a $\delta$ must fulfill additionally a locality constraint. A Turing machine changes only a single symbol in each step and moves its head to a new position in its immediate neighborhood.
 +
 
 +
Some alternative definitions of probabilistic Turing machines can be shown to be equivalent to the definition given here.
 +
* A probabilistic Turing machine can also be understood as a Turing machine $(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta_0,\delta_1)$ having two transition functions $\delta_0$ and $\delta_1$. Which one of these two functions has to be applied in the next transition step is chosen randomly with probability $1/2$ each. This can be understood as a random number generator executing a coin toss for the binary decision between two possible continuations.
 +
* In a slight variation of the above approach, a probabilsitic Turing machine is a deterministic Turing machine with an additional tape (usually considered as read-only and its head moving only to the right) containing binary random numbers. Though $\delta$ is a deterministic transition function, the additional tape introduces a random decision for each step.
 +
 
 +
===Complexity Theory of Probabilistic Turing Machines===
 +
 
 +
For a TM, the sequence of computation steps is uniquely determined. Such a machine accepts an input $x\in\Sigma^\ast$, if the terminating state of the computation is an accepting state. For a nondeterministic Turing machine, the input $x$ is accepted if it exists a computation sequence starting with $x$ and terminating in an accepting state. For probabilistic Turing machines, such a computation sequence exists in each case, even though its probability may be zero. Thus for defining acceptance, the probability of computation sequences is taken into consideration. This leads to the following definition.
 +
 
 +
For $T\colon \mathbb{N} \longrightarrow \mathbb{N}$, a PTM $M$ [[Decidable predicate|decides]] a language $L\subseteq \Sigma^\ast$ in time $T(n)$ if
 +
* For each $x\in \Sigma^\ast$ and each possible computation sequence resulting from input $x$, $M$ terminates after at most $T(|x|)$ computation steps.
 +
* $\forall x \in L \colon \mathrm{Prob}[M(x)=1 ] \ge 2/3$
 +
* $\forall x \notin L \colon \mathrm{Prob}[M(x)=0 ] \ge 2/3$
 +
In this definition, $M(x)$ designates the result of the processing of input $x$ by $M$. The expression $M(x)=1 $ indicates a termination in an accepting state, whereas $M(x)=0$ indicates a termination in a nonaccepting state. $\mathrm{Prob}[M(x)=1 ]$ denotes the fraction of computations leading to $M(x)=1$.  The class of languages decided by PTMs in $O(T(n))$ computation steps is designated as $\mathrm{BPTIME}(T(n))$.
 +
 
 +
Based on  $\mathrm{BPTIME}(T(n))$, the [[Complexity theory|complexity class]] $\mathrm{BPP}$ (an abbreviation of bounded-error, probabilistic, polynomial-time) is formally defined as
 +
$$\mathrm{BPP}:=\bigcup\limits_{c\in\mathbb{R},c>0} \mathrm{BPTIME}(|x|^c).$$
 +
This means it holds $L\in \mathrm{BPP}$ if a polynomial-time PTM $M$ exists with
 +
\begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\
 +
\forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] \ge 2/3. \end{align*}
 +
This is equivalent to  
 +
\begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\
 +
\forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 1] < 1/3. \end{align*}
 +
Since the transition function $\delta$ can be chosen in such a way that a specific continuation is preferred with a probability of $1$, a deterministic TM is a special case of a PTM. Thus it holds $\P\subseteq \mathrm{BPP}$. Up to know (2013) it is unknown, whether it holds $\mathrm{BPP} = \P$ or not.
  
===Definition of Universality===
+
The complexity class $\mathrm{BPP}$ defines the polynomial-time complexity for a PTM $M$ based on a two-sided error, i.e. $M$ may indicate $0$ despite of $x\in L$ and $1$ despite of $x\notin L$. It is also possible to define complexity classes with one-sided error. In this case, $M(x)$ may still indicate, say, a false reject, but not a false accept. This leads to the definition of the complexity class $\mathrm{RP}$ (abbreviation for random polynomial-time). It holds $L\in \mathrm{RP}$ if a polynomial-time PTM $M$ exists with
 +
\begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\
 +
\forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 0. \end{align*}
 +
This is equivalent to
 +
\begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\
 +
\forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] =1. \end{align*}
 +
An immediate consequence of the definition is the inclusion $\mathrm{RP} \subseteq \NP$, whereby $\NP$ is the complexity class of nondeterministically polynomial-time languages. Analogously, it holds $L\in \mathrm{coRP}$ if a polynomial-time PTM $M$ exists with
 +
\begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 1 \\
 +
\forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] \ge 2/3 \end{align*}
 +
or, equivalently,
 +
\begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 0] = 0 \\
 +
\forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] \ge 2/3. \end{align*}
 +
One can show both $\mathrm{RP}\subseteq \mathrm{BPP}$ and $\mathrm{coRP}\subseteq \mathrm{BPP}$. The members of $\mathrm{RP}$ gives no false accepts, while the members of $\mathrm{coRP}$ gives no false rejects. For avoiding both false accepts and rejects, i.e. false answers at all, one has to use algorithms belonging to the complexity class $\mathrm{ZPP}$.
  
A [[Turing machine]] $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ can be interpreted as partially defined function
+
The complexity class $\mathrm{ZPP}$ of zero-sided error, expected polynomial-time languages consists of all laguages $L$ for which it exists a $c\in\mathbb{R},c>0$ such that for all $x\in L$ the average running time is $|x|^c$ while the probability of providing the correct answer is equal to $1$, i.e.
$$F_T\colon\Sigma^\ast \longrightarrow \Sigma^\ast; i \mapsto
+
\begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 1 \\
\begin{cases} j &
+
\forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] = 1. \end{align*}
\text{$T$ stops in the final state $q_f\in Q$ with output $j$} \\
+
For $L\in \mathrm{ZPP}$, the probability that $M(x)$ does not terminate for $x\in L$ is equal to $0$. It holds $\mathrm{ZPP} = \mathrm{RP}\cap \mathrm{coRP}$.
\bot & \text{otherwise} \end{cases}$$
 
The definition can be generalized to multiple arguments in a canonical way. Using $F_T$, we are introducing the notions of simulation and universality. A Turing machine $U$ ''simulates'' a Turing machine $T$, if $\exists t\in\Sigma^\ast \forall s\in\Sigma^\ast \colon F_U(t, s) =F_T(s)$. The Turing machine $U$ is called ''universal'', if it can simulate every Turing machine $T$.
 
  
===Existence of an Universal Turing Machine===
+
===Improvement of Probabilistic Computations===
  
Via [[Gödelization]] it can be proven that a universal Turing machine $U$ exists. For reasons of simplicity we will assume that $U$ uses the same input/output- and band alphabet as the machine $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ to be simulated. The basic idea is for realizing $U$ is as follows: The components of $T$ are codified in $\Sigma^\ast$ giving a Gödel number $g(T)$ (W.r.o.g we assume here that the input alphatbet $\Sigma\subset^{\text{fin}}\mathbb{N}$ of $U$ is a finite subset .  Furthermore remember, that $\delta$ can be represented as a table).  The same strategy is used to codify configurations (of $T$) and computations steps (of $T$) in the alphabet $\Sigma$.  
+
The definitions of probabilistic complexity classes given above use the specific value $2/3$ as required minimal probability.  This somewhat arbitrarily chosen value can be replaced by any other value $1/2+\epsilon$, $\epsilon > 0$, without changing the essential meaning of the definitions. In the case of $\mathrm{RP}$ for example, an [[Algorithm|algorithm]] fulfilling
 +
\begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\
 +
\forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 0 \end{align*}
 +
iterated $m$ times in the case of $M(x) = 1$ leads to an algorithm fulfilling
 +
\begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge (2/3)^m  \\
 +
\forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 0. \end{align*}
 +
In the same way, algorithms belonging to the complexity class $\mathrm{coRP}$ can be modified.
  
We will designate the Turing machine $T$ with Gödel number $g(T)$ as $M_{g(T)}$ in the following. Now, a Turing machine $U$ can simulate $M_{g(T)}$ using its Gödel number $g(T)$. Assuming $M_{g(T)}$ is given the input $s$, the machine $U$ translates $s$ to the corresponding start configuration $c_s\in C$ of $T$. Afterwards, $U$ simulates each calculation step of $M_{g(T)}$ by looping over the following operation sequence
+
Algorithms belonging to the complexity class $\mathrm{BPP}$ require some more effort for modifying the probability of correctness. Here, an $m$-fold repetition is used, whereby the results $b_1,\ldots,b_m$ are evaluated using a voting mechanism. Assuming that $M(x)$ decides the predicate $x\in L$ by producing the result $0$ or $1$ and that $m$ is an odd number, the modified algorithm gives $1$ if $\sum_i b_i > m/2$ and $0$ otherwise. The probability of correctness is modified according to Chernoff bounds as follows.
* Identify the actual configuration $c$ of the simulated Turing machine $M_{g(T)}$  
 
* Identify the transition operation to be applied to $c$ according to the (codified) transition function $\delta$ of $M_{g(T)}$
 
* Update the old configuration $c$ to the new configuration $c'$ using the identified transition operation
 
* Stop executing the loop if either no suitable transition operation exist (remember that $\delta$ is a partial function) or if in $c'= (B,i,q)$ it holds $q=q_f$.
 
Invalid Gödel numbers are assigned to a Turing machine looping for all inputs.  In effect, this gives $ U(g(T),s) = M_{g(T)}(s) $ for all $s\in\Sigma^\ast$.
 
  
===Interpretation of Universality===
+
Let $x_1,\ldots,x_m$ be independent random variables having the same probability distribution with image set $\{0,1\}$. For $p:= \mathrm{Prob}[x_i=1]$, $X:=\sum_{i=1}^mx_i$, and $\Theta \in [0,1]$ it holds
 +
$$\begin{array}{rcl}
 +
\mathrm{Prob}[X\ge (1+\Theta)pm] &\le & \exp\left(-{\Theta^2\over 3}pm\right) \\
 +
\mathrm{Prob}[X\le (1-\Theta)pm] &\le & \exp\left(-{\Theta^2\over 2}pm\right)
 +
\end{array}$$
 +
According to the definition of the class $\mathrm{BPP}$, it holds $p=2/3$.  Taking $\Theta=1/4$ in the second Chernoff bound gives
 +
$$\mathrm{Prob}[X\le m/2] \le \exp\left(-{\Theta^2\over 2}pm\right) = \exp\left(-{1\over 48}m\right) $$
 +
i.e. the error of the voting algorithm is smaller or equal to $\exp(-{m/48})$.
  
The universality property shows that Turing machines are quite powerful instruments. A Turing machine equipped with a suitable transition function $\delta$ can simulate each other Turing machine. For the other members of the Chomsky-hierarchy this closure property does not hold. Universality has far-reaching consequences for practice. It assures the usability for general purposes, i.e. the adaptability to all possible computable tasks by using a corresponding ''program'' as input.
+
===Applications of Probabilistic Computations===
  
On the other hand, universality is a strong limitation as well. It exist an uncountable number of functions $f\colon\mathbb{N}\rightarrow\mathbb{N}$, but for a universal machine only a countable subset of them is computable. This is caused by the necessary usage of a [[Gödelization]].
+
Some examples for probabilistic algorithms may be given. Only their basic ideas are presented.
 +
* The probabilistic primality testing for a natural number $n\in\mathbb{N}$ can be realized as follows: Generate random natural numbers $k_1, \ldots, k_r$ with $1 < k_i < n$. For each $k_i$, calculate the greatest common divisor $g_i:=\gcd(n,k_i)$. If it exists a $i$ with $g_i>1$, output $0$ for 'not prime'. Otherwise, output $1$.
 +
* The question, whether two polynomials $f(x)$, $g(x)$ are equal on a region $D$ can be reduced to the question, whether $f(x)-g(x)=0$ for $x\in D$. Thus, the algorithm generates random numbers $x_1, \ldots, x_r$ with $x_i \in D$. For each $x_i$, the algorithm calculates the difference $d_i:= f(x_i)-g(x_i)$. If it exists a $i$ with $d_i\neq 0$, output $0$ representing 'unequal'. Otherwise, output $1$ representing 'equal'.
  
 
===References===
 
===References===
Line 36: Line 93:
 
{|
 
{|
 
|-
 
|-
|valign="top"|{{Ref|H77}}||valign="top"| F. Hennie, "Introduction to Computability", Addison-Wesley 1977
+
|valign="top"|{{Ref|DK2000}}||valign="top"| Ding-Zhu Du, Ker-I Ko, \"Theory of Computational Complexity\", Wiley 2000
 
|-
 
|-
|valign="top"|{{Ref|HU79}}||valign="top"| J. Hopcroft, J. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley 1979
+
|valign="top"|{{Ref|AB2009}}||valign="top"| Sanjeev Arora, Boaz Barak, \"Computational Complexity: A Modern Approach\", Cambridge University Press 2009
 
|-
 
|-
|valign="top"|{{Ref|P81}}||valign="top"| C. Papdimitriou, "Elements of the theory of computation", Prentice-Hall 1981
+
|valign="top"|{{Ref|BC2006}}||valign="top"| [parlevink.cs.utwente.nl/~vdhoeven/CCC/bCC.pdf Daniel Pierre Bovet, Pierluigi Crescenzim, \"Introduction to the Theory of Complexity\", 2006]
 
|-
 
|-
 
|}
 
|}

Revision as of 16:47, 26 December 2013



2020 Mathematics Subject Classification: Primary: 68Q05 [MSN][ZBL]


A probabilistic Turing machine (PTM) is a Turing machine (TM) modified for executing a randomized computation. From the computability point of view, a PTM is equivalent to a TM. In other respects, however, the behavior of a PTM is profoundly different from the deterministic computation of a TM; false results, for example, can only be excluded statistically in this model. The physical realization of a true random number generation is possible by performing a measurement process in quantum theory.

Some applications of computer science can be better modeled by a PTM than by a classical TM. An example are environments with strong radiation like space missions crossing the radiation belt of Jupiter or robots for handling accidents in a nuclear plant. But even a usual calculation involving a very large number of single operations (e.g. calculations of $\pi$ with record precision) may be potentially influenced by cosmic rays making the calculation probabilistic.

Definition of a Probabilistic Turing Machine

A PTM $(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ has the same components as a TM. The set $Q$ is a finite set of states, $\Sigma$ is a finite input/output alphabet, $\Gamma$ is a finite tape alphabet with $\Sigma\subseteq\Gamma$, $\sqcup\in \Gamma$ is a blank symbol with $\sqcup \notin \Sigma$, the state $q_0 \in Q$ is a start state, and $q_f \in Q$ is a stop state. The transition function $\delta$, however, does not define deterministic transitions as in the case of a Turing machine, but gives a probability distribution of possible transitions according to $ \delta: Q \times \Sigma \times Q \times \Sigma \times \set{L,R} \longrightarrow [0,1]$.

For probabilistic Turing machines, the set $C$ of configurations is defined in the same way as for Turing machines. It is also called the set of basic states. The set $\Omega$ of states is the set of possible probability distributions on the basic states, i.e. $\Omega=\{(p_c)_{c\in C}\in [0,1]^C\mid \sum_{c\in C} p_c=1\}$. The set of states serves as memory for the computation history. Since the run of the computation is probabilistic, the definition of a state must be probabilistic as well. Thus the distinction between basic states and states.

The transition function $\delta$ can be considered as stochastic matrix $M_{ji}$ defined on the space $C$ of configurations with $ M_{ji} = \mathrm{Prob}[\delta\colon c_i \mapsto c_j] \in [0,1]$. As a stochastic matrix, the $L_1$-norm of each column of $M_{ji}$ is equal to 1, i.e. $\sum_i M_{ji} = 1$. $L_1$-norms are preserved by $M$ according to $L_1(M\cdot c) = L_1(c) = \sum_{i} c_i$ for a configuration $c\in C$. Not every stochastic matrix provides the transition function $\delta$ of a PTM, however, because such a $\delta$ must fulfill additionally a locality constraint. A Turing machine changes only a single symbol in each step and moves its head to a new position in its immediate neighborhood.

Some alternative definitions of probabilistic Turing machines can be shown to be equivalent to the definition given here.

  • A probabilistic Turing machine can also be understood as a Turing machine $(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta_0,\delta_1)$ having two transition functions $\delta_0$ and $\delta_1$. Which one of these two functions has to be applied in the next transition step is chosen randomly with probability $1/2$ each. This can be understood as a random number generator executing a coin toss for the binary decision between two possible continuations.
  • In a slight variation of the above approach, a probabilsitic Turing machine is a deterministic Turing machine with an additional tape (usually considered as read-only and its head moving only to the right) containing binary random numbers. Though $\delta$ is a deterministic transition function, the additional tape introduces a random decision for each step.

Complexity Theory of Probabilistic Turing Machines

For a TM, the sequence of computation steps is uniquely determined. Such a machine accepts an input $x\in\Sigma^\ast$, if the terminating state of the computation is an accepting state. For a nondeterministic Turing machine, the input $x$ is accepted if it exists a computation sequence starting with $x$ and terminating in an accepting state. For probabilistic Turing machines, such a computation sequence exists in each case, even though its probability may be zero. Thus for defining acceptance, the probability of computation sequences is taken into consideration. This leads to the following definition.

For $T\colon \mathbb{N} \longrightarrow \mathbb{N}$, a PTM $M$ decides a language $L\subseteq \Sigma^\ast$ in time $T(n)$ if

  • For each $x\in \Sigma^\ast$ and each possible computation sequence resulting from input $x$, $M$ terminates after at most $T(|x|)$ computation steps.
  • $\forall x \in L \colon \mathrm{Prob}[M(x)=1 ] \ge 2/3$
  • $\forall x \notin L \colon \mathrm{Prob}[M(x)=0 ] \ge 2/3$

In this definition, $M(x)$ designates the result of the processing of input $x$ by $M$. The expression $M(x)=1 $ indicates a termination in an accepting state, whereas $M(x)=0$ indicates a termination in a nonaccepting state. $\mathrm{Prob}[M(x)=1 ]$ denotes the fraction of computations leading to $M(x)=1$. The class of languages decided by PTMs in $O(T(n))$ computation steps is designated as $\mathrm{BPTIME}(T(n))$.

Based on $\mathrm{BPTIME}(T(n))$, the complexity class $\mathrm{BPP}$ (an abbreviation of bounded-error, probabilistic, polynomial-time) is formally defined as $$\mathrm{BPP}:=\bigcup\limits_{c\in\mathbb{R},c>0} \mathrm{BPTIME}(|x|^c).$$ This means it holds $L\in \mathrm{BPP}$ if a polynomial-time PTM $M$ exists with \begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\ \forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] \ge 2/3. \end{align*} This is equivalent to \begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\ \forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 1] < 1/3. \end{align*} Since the transition function $\delta$ can be chosen in such a way that a specific continuation is preferred with a probability of $1$, a deterministic TM is a special case of a PTM. Thus it holds $\P\subseteq \mathrm{BPP}$. Up to know (2013) it is unknown, whether it holds $\mathrm{BPP} = \P$ or not.

The complexity class $\mathrm{BPP}$ defines the polynomial-time complexity for a PTM $M$ based on a two-sided error, i.e. $M$ may indicate $0$ despite of $x\in L$ and $1$ despite of $x\notin L$. It is also possible to define complexity classes with one-sided error. In this case, $M(x)$ may still indicate, say, a false reject, but not a false accept. This leads to the definition of the complexity class $\mathrm{RP}$ (abbreviation for random polynomial-time). It holds $L\in \mathrm{RP}$ if a polynomial-time PTM $M$ exists with \begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\ \forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 0. \end{align*} This is equivalent to \begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\ \forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] =1. \end{align*} An immediate consequence of the definition is the inclusion $\mathrm{RP} \subseteq \NP$, whereby $\NP$ is the complexity class of nondeterministically polynomial-time languages. Analogously, it holds $L\in \mathrm{coRP}$ if a polynomial-time PTM $M$ exists with \begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 1 \\ \forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] \ge 2/3 \end{align*} or, equivalently, \begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 0] = 0 \\ \forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] \ge 2/3. \end{align*} One can show both $\mathrm{RP}\subseteq \mathrm{BPP}$ and $\mathrm{coRP}\subseteq \mathrm{BPP}$. The members of $\mathrm{RP}$ gives no false accepts, while the members of $\mathrm{coRP}$ gives no false rejects. For avoiding both false accepts and rejects, i.e. false answers at all, one has to use algorithms belonging to the complexity class $\mathrm{ZPP}$.

The complexity class $\mathrm{ZPP}$ of zero-sided error, expected polynomial-time languages consists of all laguages $L$ for which it exists a $c\in\mathbb{R},c>0$ such that for all $x\in L$ the average running time is $|x|^c$ while the probability of providing the correct answer is equal to $1$, i.e. \begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 1 \\ \forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 0] = 1. \end{align*} For $L\in \mathrm{ZPP}$, the probability that $M(x)$ does not terminate for $x\in L$ is equal to $0$. It holds $\mathrm{ZPP} = \mathrm{RP}\cap \mathrm{coRP}$.

Improvement of Probabilistic Computations

The definitions of probabilistic complexity classes given above use the specific value $2/3$ as required minimal probability. This somewhat arbitrarily chosen value can be replaced by any other value $1/2+\epsilon$, $\epsilon > 0$, without changing the essential meaning of the definitions. In the case of $\mathrm{RP}$ for example, an algorithm fulfilling \begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge 2/3 \\ \forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 0 \end{align*} iterated $m$ times in the case of $M(x) = 1$ leads to an algorithm fulfilling \begin{align*}\forall x \in L \colon & \,\, \mathrm{Prob}[M(x) = 1] \ge (2/3)^m \\ \forall x \notin L \colon & \,\, \mathrm{Prob}[M(x) = 1] = 0. \end{align*} In the same way, algorithms belonging to the complexity class $\mathrm{coRP}$ can be modified.

Algorithms belonging to the complexity class $\mathrm{BPP}$ require some more effort for modifying the probability of correctness. Here, an $m$-fold repetition is used, whereby the results $b_1,\ldots,b_m$ are evaluated using a voting mechanism. Assuming that $M(x)$ decides the predicate $x\in L$ by producing the result $0$ or $1$ and that $m$ is an odd number, the modified algorithm gives $1$ if $\sum_i b_i > m/2$ and $0$ otherwise. The probability of correctness is modified according to Chernoff bounds as follows.

Let $x_1,\ldots,x_m$ be independent random variables having the same probability distribution with image set $\{0,1\}$. For $p:= \mathrm{Prob}[x_i=1]$, $X:=\sum_{i=1}^mx_i$, and $\Theta \in [0,1]$ it holds $$\begin{array}{rcl} \mathrm{Prob}[X\ge (1+\Theta)pm] &\le & \exp\left(-{\Theta^2\over 3}pm\right) \\ \mathrm{Prob}[X\le (1-\Theta)pm] &\le & \exp\left(-{\Theta^2\over 2}pm\right) \end{array}$$ According to the definition of the class $\mathrm{BPP}$, it holds $p=2/3$. Taking $\Theta=1/4$ in the second Chernoff bound gives $$\mathrm{Prob}[X\le m/2] \le \exp\left(-{\Theta^2\over 2}pm\right) = \exp\left(-{1\over 48}m\right) $$ i.e. the error of the voting algorithm is smaller or equal to $\exp(-{m/48})$.

Applications of Probabilistic Computations

Some examples for probabilistic algorithms may be given. Only their basic ideas are presented.

  • The probabilistic primality testing for a natural number $n\in\mathbb{N}$ can be realized as follows: Generate random natural numbers $k_1, \ldots, k_r$ with $1 < k_i < n$. For each $k_i$, calculate the greatest common divisor $g_i:=\gcd(n,k_i)$. If it exists a $i$ with $g_i>1$, output $0$ for 'not prime'. Otherwise, output $1$.
  • The question, whether two polynomials $f(x)$, $g(x)$ are equal on a region $D$ can be reduced to the question, whether $f(x)-g(x)=0$ for $x\in D$. Thus, the algorithm generates random numbers $x_1, \ldots, x_r$ with $x_i \in D$. For each $x_i$, the algorithm calculates the difference $d_i:= f(x_i)-g(x_i)$. If it exists a $i$ with $d_i\neq 0$, output $0$ representing 'unequal'. Otherwise, output $1$ representing 'equal'.

References

[DK2000] Ding-Zhu Du, Ker-I Ko, \"Theory of Computational Complexity\", Wiley 2000
[AB2009] Sanjeev Arora, Boaz Barak, \"Computational Complexity: A Modern Approach\", Cambridge University Press 2009
[BC2006] [parlevink.cs.utwente.nl/~vdhoeven/CCC/bCC.pdf Daniel Pierre Bovet, Pierluigi Crescenzim, \"Introduction to the Theory of Complexity\", 2006]
How to Cite This Entry:
Joachim Draeger/sandbox. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Joachim_Draeger/sandbox&oldid=31199