RL (complexity class)

In complexity theory , RL is the class of decision problems that can be solved by a probabilistic Turing machine on logarithmic space with a limited one-sided error probability.

definition

A language, i.e. a subset , belongs to the class RL if there is a probabilistic Turing machine such that the following applies: ${\ displaystyle L \ subset \ {0.1 \} ^ {*}}$ ${\ displaystyle M}$

There is a constant so that any possible calculation uses at most cells on one input per work band . ${\ displaystyle C> 0}$ ${\ displaystyle M}$ ${\ displaystyle x \ in \ {0.1 \} ^ {n}}$ ${\ displaystyle C \ cdot \ log n}$
Is , then (limited probability of error at ) ${\ displaystyle x \ in L}$ ${\ displaystyle P (M (x) = 1) \ geq \ textstyle {\ frac {2} {3}}}$ ${\ displaystyle x \ in L}$
Is , so is (no mistake about ) ${\ displaystyle x \ notin L}$ ${\ displaystyle P (M (x) = 1) = 0}$ ${\ displaystyle x \ notin L}$

It means the result of a random calculation of the machine on the input . The probability relates to all possible calculations. The seemingly arbitrary probability can be replaced by any number without changing the class RL . ${\ displaystyle M (x)}$ ${\ displaystyle M}$ ${\ displaystyle x}$ ${\ displaystyle P}$ ${\ displaystyle \ textstyle {\ frac {2} {3}}}$ ${\ displaystyle 0 <p <1}$

Relationships to other complexity classes

L RL NL applies . ${\ displaystyle \ subset}$ ${\ displaystyle \ subset}$

The first inclusion applies, since every deterministic Turing machine with logarithmic space requirements, that is to say decides languages from L , can also be understood as a probabilistic Turing machine with the above properties. The second inclusion is also clear, since a language already belongs to NL if a decisive probabilistic Turing machine (with logarithmic space requirements) has an accepting invoice run.

Path in undirected graph

The following algorithm of such a Turing machine is known, which decides whether there is a connecting path in an undirected graph with nodes to two specified nodes . The language is the set of all binary codings of triples of graphs and two of their nodes and for which there is a connecting path. This language is also called UPATH (for undirected path) ${\ displaystyle n}$ ${\ displaystyle (G, s, t)}$ ${\ displaystyle G}$ ${\ displaystyle s}$ ${\ displaystyle t}$

A UPATH decisive algorithm in the sense of the above definition proceeds as follows: You start a random walk along the edges of the graph and stop after steps or when it has been reached. In the latter case you output 1, otherwise 0. ${\ displaystyle s}$ ${\ displaystyle 100n ^ {4}}$ ${\ displaystyle t}$

The space requirement of this algorithm includes a counter for the number of steps and a memory for the current node of the random walk, both of which are feasible with a constant multiple of . The algorithm, that is, the associated probabilistic Turing machine, thus fulfills the first of the three conditions. It can be shown that because of the sufficiently high number of steps , the second condition is also fulfilled, i.e. the algorithm finds it with a sufficiently high probability if the coding of is in UPATH. Otherwise, ie if from out can not be reached, the algorithm only 0 can output, as the random walk can never reach. This also fulfills the third condition. ${\ displaystyle \ log n}$ ${\ displaystyle 100n ^ {4}}$ ${\ displaystyle t}$ ${\ displaystyle (G, s, t)}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle t}$

To solve this problem, however, one does not have to resort to probabilistic Turing machines. Omer Reingold showed in 2005 that UPATH is even in the complexity class L , i.e. a decision can even be made deterministically with logarithmic space requirements.

Individual evidence

↑ Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , Section 7.7: Randomized Space-Bounded Computation
↑ R. Aleliunas, RM Karp, L. Lipton, L. Lovász, C. Rackoff: Random walks, universal traversal sequences, and the complexity of maze problems (1979), pages 218-233 FOCS (54th Annual Symposium on Foundations of Computer Science)
^ Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , Theorem 21.21: Reingold's Theorem

[1] Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , Section 7.7: Randomized Space-Bounded Computation

[2] R. Aleliunas, RM Karp, L. Lipton, L. Lovász, C. Rackoff: Random walks, universal traversal sequences, and the complexity of maze problems (1979), pages 218-233 FOCS (54th Annual Symposium on Foundations of Computer Science)

[3] Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 978-0-521-42426-4 , Theorem 21.21: Reingold's Theorem