Namespaces
Variants
Actions

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

From Encyclopedia of Mathematics
Jump to: navigation, search
 
(12 intermediate revisions by the same user not shown)
Line 1: Line 1:
  
$\Sigma$-Algebra
+
{{MSC|68Q05}}
  
{{MSC|68P05}}  
+
{{TEX|done}}
  
{{TEX|done}}
+
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 \{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=\left\{(p_c)_{c\in C}\in [0,1]^C \,\,\,\left| \,\,\,\sum\limits_{c\in C} p_c=1\right.\right\}.$$
 +
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.
  
$\Sigma$-Algebras are the [[Semantics|semantical]] counterpart to the [[Signature (Computer Science)|signatures]], which are pure syntactical objects. In order to give the function symbols $f\in F$ of a signature $\Sigma=(S,F)$ a meaning, a (total) $\Sigma$-algebra provides an object with the same structure as $\Sigma$ but consisting of concrete elements and concrete functions operating on these elements.  The elements and functions of a $\Sigma$-algebra are the counterparts to the sorts and function symbols of the signature $\Sigma$.
+
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.
  
===Definition of $\Sigma$-Algebras===
+
===Complexity Theory of Probabilistic Turing Machines===
  
Formally, a $\Sigma$-algebra $A=((s^A)_{s\in S},(f^A)_{f\in F})$ consists of a family $(s^A)_{s\in S}$ of <i>carrier sets</i> $s^A$ corresponding to the sorts $s\in S$ and a family $(f^A)_{f\in F}$ of functions on these carrier sets corresponding to the function symbols $f\in F$. The compatibility requirement is that for a function symbol $f$ of type$(f)= s_1\times\cdots\times s_n \longrightarrow s$, the function $f^A$ must have the form $f^A\colon s_1^A\times\cdots\times s_n^A \longrightarrow s^A$.
+
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.
  
===Category of $\Sigma$-Algebras===
+
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))$.
  
Let $\Sigma=(S,F)$ be a signature and let $A,B$ be $\Sigma$-algebras.  A $\Sigma$-algebra-morphism $m\colon A\longrightarrow B$ is a family $(m_s\colon s^A \longrightarrow s^B)_{s\in S}$ of mappings between the carrier sets of $A,B$ fulfilling the following compatibility properties
+
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
* $m_s(f^A)= f^B$ for $f\in F$ with ar$(f)=0$ and $\mathrm{type}(f)=\,\, \rightarrow s\}$
+
$$\mathrm{BPP}:=\bigcup\limits_{c\in\mathbb{R},c>0} \mathrm{BPTIME}(|x|^c).$$
* $m_s(f^A(a_1,\ldots,a_n))=f^B(m_{s_1}(a_1),\ldots,m_{s_n}(a_n))$ for $f\in F$ with $\mathrm{type}(f)= s_1\times\cdots\times s_n \longrightarrow s$ and for $a_i\in s_i^A$.
+
This means it holds $L\in \mathrm{BPP}$ if a polynomial-time PTM $M$ exists with
The class of $\Sigma$-algebras together with the $\Sigma$-algebra-morphisms forms a [[Category|category]] {{Cite|W90}}.
+
\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*}
 +
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 $\mathrm{P}\subseteq \mathrm{BPP}$. Up to know (2013) it is unknown, whether it holds $\mathrm{BPP} = \mathrm{P}$ or not.
  
The option to use partially defined functions complicates the situation considerably and leads to refined versions of the definition. Though this does not belong to the scope of this entry, a short remarks seems to be appropriate. For example it is possible under this generalization that $m_s(f^A(a_1,\ldots,a_n))$ is undefined though $f^A(a_1,\ldots,a_n)$ is defined. This can be caused by an undefinedness of a term $m_{s_j}(a_j)$ or of $f^B(m_{s_1}(a_1),\ldots,m_{s_n}(a_n))$ {{Cite|M89}}.
+
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 \mathrm{NP}$, whereby $\mathrm{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}$.  
  
===$\Sigma$-Subalgebras===
+
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}$.
  
One can easily imagine that typically many different $\Sigma$-algebras exist for the same signature $\Sigma$. This holds even in the case of [[Algebraic Specification|algebraic specifications]], which can restrict the set of admissable $\Sigma$-algebras by additional [[Axiom|axioms]]. In effect, this means that an abstract signature $\Sigma$ can be 'implemented' by concrete $\Sigma$-algebras with different semantics. This leads to an interest in the relationships between these $\Sigma$-algebras. One method to discuss the relationships is to use $\Sigma$-algebra-morphisms, another is the notion of $\Sigma$-subalgebras.
+
===Improvement of Probabilistic Computations===
  
$\Sigma$-Subalgebras of $\Sigma$-algebras are defined in the usual wayA $\Sigma$-Algebra $A$ is called a <i>$\Sigma$-subalgebra</i> of a $\Sigma$-Algebra $B$, if $\forall s\in S\colon s^A\subseteq s^B$ and if $f^A(a_1,\ldots,a_n) = f^B(a_1,\ldots,a_n)$ for $f\in F$ with $\mathrm{type}(f)= s_1\times\cdots\times s_n \longrightarrow s$ and for $a_i\in s_i^A$. The subalgebra-property is written as $A\subseteq B$.
+
The definitions of probabilistic complexity classes given above use the specific value $2/3$ as required minimal probabilityThis 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.
  
Another way to characterize the subalgebra-property is the existence of a $\Sigma$-algebra-morphism $m\colon A\longrightarrow B$, which is the identity on each carrier set of $A$, i.e. $m=(\mathrm{id}_{s^A})_{s\in S}$.
+
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.
  
(Carriers of) $\Sigma$-Subalgebras are closed under [[Intersection of sets|intersection]]. For a family $((s^{A_i})_{s\in S},(f^{A_i})_{f\in F})_{i\in I}$ of $\Sigma$-subalgebras $A_i$, their intersection $A=((s^{A})_{s\in S}, (f^{A})_{f\in F})$ is a $\Sigma$-subalgebra given by carrier sets $s^A:= \bigcap\limits_{i\in I} s^{A_i}$ for all $s\in S$ and functions $f^A:= f^{A_k}|_{s^A}$ for all $f\in F$ for an arbitrarily chosen $k\in I$. The declaration $f^A$ is well-defined, because according to the definition of a $\Sigma$-subalgebra the functions $f^{A_i}$ must behave in the same way on $s^A$.
+
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}$$
 +
The random variables $x_i$ are now interpreted as error variables, i.e.  $x_i=1$ if the $i$-th repetition of the decision algorithm gives a wrong answer and $x_i=0$ otherwise. According to the definition of the class $\mathrm{BPP}$, it holds $p=1-2/3=1/3$.  Taking $\Theta=1/2$ in the first Chernoff bound gives
 +
$$\mathrm{Prob}[X\ge m/2] \le \exp\left(-{\Theta^2\over 3}pm\right) = \exp\left(-{1\over 36}m\right) $$
 +
i.e. the error of the voting algorithm is smaller or equal to $\exp(-{m/36})$.
  
The closedness of the set of $\Sigma$-subalgebras under intersections has an important consequence. For a $\Sigma$-algebra $A=((s^A)_{s\in S}, (f^A)_{f\in F})$ and an $S$-sorted set $X=(\bar s)_{s\in S}$ with $\bar s\subseteq s^A$ for all $s\in S$, it assures the existence of a smallest $\Sigma$-subalgebra $A'\subseteq A$ of $A$ containing $X$, i.e.  $\bar s\subseteq s^{A'}$. The $\Sigma$-algebra $A'$ is called the $\Sigma$-subalgebra of $A$ <i>generated</i> by $X$ {{Cite|ST99}}.
+
===Applications of Probabilistic Computations===
  
The subalgebra-property is compatible with $\Sigma$-algebra-morphisms.  Let $A,B$ be $\Sigma$-algebras and let $m=(m_s)_{s\in S}\colon A \longrightarrow B$ be a $\Sigma$-algebra-morphism. For a $\Sigma$-subalgebra $A'\subseteq A$ of $A$, its image $m(A')\subseteq B$ is a $\Sigma$-subalgebra of $B$. The expression $B':=m(A')$ is defined in the obvious way, i.e. for $A'=((s^{A'})_{s\in S},(f^{A'})_{f\in F})$ the $\Sigma$-subalgebra $B'=((s^{B'})_{s\in S},(f^{B'})_{f\in F})$ is given by $s^{B'}:=\{m_s(a)|a\in s^{A'}\}$ for all $s\in S$ and $f_{B'}(m_{s_1}(a_1),\ldots,m_{s_n}(a_n)) = m_s(f_{A'}(a_1,\ldots,a_n))$ for all function symbols $f \colon s_1 \times \ldots\times s_n \longrightarrow s$ with $f\in F$ and $a_i \in s_i^{A'}$. The coimage of a $\Sigma$-subalgebra $B'\subseteq B$ of $B$ under $m$ is a $\Sigma$-subalgebra $m^{-1}(B')\subseteq A$ of $A$. The expression $m^{-1}(B')$ can be defined analogously to $m(A')$ and is omitted here {{Cite|ST99}}.
+
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 39: Line 89:
 
{|
 
{|
 
|-
 
|-
|valign="top"|{{Ref|EM85}}||valign="top"| H. Ehrig, B. Mahr: "Fundamentals of Algebraic Specifications", Volume 1, Springer 1985
+
|valign="top"|{{Ref|DK2000}}||valign="top"| Ding-Zhu Du, Ker-I Ko, "Theory of Computational Complexity", Wiley 2000
|-
 
|valign="top"|{{Ref|EM90}}||valign="top"| H. Ehrig, B. Mahr: "Fundamentals of Algebraic Specifications", Volume 2, Springer 1990
 
|-
 
|valign="top"|{{Ref|M89}}||valign="top"| B. Möller: "Algorithmische Sprachen und Methodik des Programmierens I", lecture notes, Technical University Munich 1989
 
 
|-
 
|-
|valign="top"|{{Ref|ST99}}||valign="top"| D. Sannella, A. Tarlecki, "Algebraic Preliminaries ", in Egidio Astesiano, Hans-Joerg Kreowski, Bernd Krieg-Brueckner, "Algebraic Foundations of System Specification", Springer 1999
+
|valign="top"|{{Ref|AB2009}}||valign="top"| Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach", Cambridge University Press 2009
 
|-
 
|-
|valign="top"|{{Ref|W90}}||valign="top"| M. Wirsing: "Algebraic Specification", in J. van Leeuwen: "Handbook of Theoretical Computer Science", Elsevier 1990
+
|valign="top"|{{Ref|BC2006}}||valign="top"| [http://parlevink.cs.utwente.nl/~vdhoeven/CCC/bCC.pdf Daniel Pierre Bovet, Pierluigi Crescenzim, "Introduction to the Theory of Complexity", 2006]
 
|-
 
|-
 
|}
 
|}

Latest revision as of 17:42, 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 \{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=\left\{(p_c)_{c\in C}\in [0,1]^C \,\,\,\left| \,\,\,\sum\limits_{c\in C} p_c=1\right.\right\}.$$ 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*} 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 $\mathrm{P}\subseteq \mathrm{BPP}$. Up to know (2013) it is unknown, whether it holds $\mathrm{BPP} = \mathrm{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 \mathrm{NP}$, whereby $\mathrm{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}$$ The random variables $x_i$ are now interpreted as error variables, i.e. $x_i=1$ if the $i$-th repetition of the decision algorithm gives a wrong answer and $x_i=0$ otherwise. According to the definition of the class $\mathrm{BPP}$, it holds $p=1-2/3=1/3$. Taking $\Theta=1/2$ in the first Chernoff bound gives $$\mathrm{Prob}[X\ge m/2] \le \exp\left(-{\Theta^2\over 3}pm\right) = \exp\left(-{1\over 36}m\right) $$ i.e. the error of the voting algorithm is smaller or equal to $\exp(-{m/36})$.

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] 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=29376