Alternating Turing machine

In theoretical computer science , an alternating Turing machine (ATM) is a nondeterministic Turing machine that extends the usual rules for accepting an input. The states of the machine are divided into existential and universal states. The first accept an input if there is a possible computation that accepts, while the second accept only when all possible computations accept.

Informal description

Since alternating Turing machines are nondeterministic machines, there are several options for continuing the calculation for each configuration of the machine. To define classes like NP , one assumes that an input is accepted if there is a computation that accepts it. On the other hand, to define machines for coNP problems, one assumes that a word is only accepted if it accepts all possible calculations.

Alternating machines combine these two modes by dividing the states into existential and universal states. If a configuration has an existential state, it is viewed as accepting as soon as only one successor configuration is accepted, while a configuration with a universal state only accepts if all successor configurations accept. An entry is accepted if the associated initial configuration accepts.

Formal definition

An alternating Turing machine with k-bands is a tuple with ${\ displaystyle A = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, \ square, g)}$

${\ displaystyle Q}$ is a finite non-empty set (set of states)
${\ displaystyle \ Sigma}$ is a finite non-empty set (input alphabet)
${\ displaystyle \ Gamma}$ is a finite non-empty set (ribbon alphabet), where ${\ displaystyle \ Gamma \ supseteq \ Sigma}$
${\ displaystyle \ delta \ subseteq Q \ times \ Gamma ^ {k} \ times Q \ times \ Gamma ^ {k} \ times \ {L, N, R \} ^ {k}}$ is the transition relation
${\ displaystyle q_ {0} \ in Q}$ is the start state
${\ displaystyle \ square \ in \ Gamma}$ is the blank symbol
${\ displaystyle g \ colon Q \ rightarrow \ {\ wedge, \ vee, \ operatorname {accept}, \ operatorname {reject} \}}$ a function that assigns a type to each state

Acceptance of input

Now consider a configuration of such a machine with the state : ${\ displaystyle C}$ ${\ displaystyle q \ in Q}$

If so , then it is an accepting (end) configuration. ${\ displaystyle g (q) = \ operatorname {accept}}$ ${\ displaystyle C}$
If so , then it is a non-accepting (end) configuration. ${\ displaystyle g (q) = \ operatorname {reject}}$ ${\ displaystyle C}$
If so , then an accepting configuration is if and only if all successor configurations are accepting configurations. Otherwise is a non-accepting configuration. ${\ displaystyle g (q) = \ wedge}$ ${\ displaystyle C}$ ${\ displaystyle C}$
If then there is an accepting configuration, if there is an accepting successor configuration. Otherwise is a non-accepting configuration. ${\ displaystyle g (q) = \ vee}$ ${\ displaystyle C}$ ${\ displaystyle C}$

An alternating Turing machine accepts an input if and only if the initial configuration is an accepting configuration.

Complexity theory

As with deterministic and non-deterministic Turing machines, time and space complexity can also be defined for alternating Turing machines .

In order to calculate the value of a configuration, not all successors necessarily have to be evaluated. An existential configuration is surely accepting as soon as a successor accepts (regardless of the value of the remaining successors), and a universal configuration is non-accepting as soon as a successor does not accept. For an efficient calculation, not all configurations have to be evaluated, and this is also taken into account in the following definitions of and . ${\ displaystyle ATIME}$ ${\ displaystyle ASPACE}$

An ATM that decides a language decides this in time if all calculation paths from evaluated configurations are no longer than for each input . The set of all languages that can be decided in time by an ATM is recorded as . ${\ displaystyle A}$ ${\ displaystyle L}$ ${\ displaystyle t (n)}$ ${\ displaystyle x}$ ${\ displaystyle t (| x |)}$ ${\ displaystyle t (n)}$ ${\ displaystyle ATIME (t (n))}$

An ATM that decides a language decides this in place if for each input all evaluated configurations on all bands are no longer used as cells. The set of all languages that can be decided into place by an ATM is recorded as . ${\ displaystyle A}$ ${\ displaystyle L}$ ${\ displaystyle s (n)}$ ${\ displaystyle x}$ ${\ displaystyle s (| x |)}$ ${\ displaystyle s (n)}$ ${\ displaystyle ASPACE (s (n))}$

Complexity classes

The following complexity classes closed under (log n) reductions via ATMs are common:

${\ displaystyle ALOGSPACE = ASPACE (\ log n)}$ Alternating logarithmic space
${\ displaystyle AP = \ bigcup _ {k> 0} ATIME (n ^ {k})}$ Alternating polynomial time
${\ displaystyle APSPACE = \ bigcup _ {k> 0} ASPACE (n ^ {k})}$ Alternating polynomial space
${\ displaystyle AEXPTIME = \ bigcup _ {k> 0} ATIME (k ^ {n})}$ Alternating exponential time

Relation to other machine models

The following relationships apply between alternating and deterministic complexity:

{\ displaystyle ATIME (f (n)) \ subseteq SPACE (f (n)) \ qquad \ qquad f (n) \ geq n}

{\ displaystyle ASPACE (f (n)) = \ bigcup _ {c> 0} TIME (c ^ {f (n)}) \ qquad \ qquad f (n) \ geq \ log {n}}

In particular, the complexity classes defined above correspond to the usual deterministic complexity classes:

ALOGSPACE = Ptime
AP = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE

ATMs can also be used to characterize the LOGCFL class .

Limited alternations

One can also consider alternating Turing machines that can only perform a limited number of changes between existential and universal states. One defines (or ) as the set of all languages that are decided by an ATM in time , whose initial state is an existential (or universal) state and which changes between existential and universal states at most times on each possible calculation path . ${\ displaystyle \ Sigma _ {i} TIME (t (n))}$ ${\ displaystyle \ Pi _ {i} TIME (t (n))}$ ${\ displaystyle t (n)}$ ${\ displaystyle i-1}$

Alternating Turing machines with limited alternations are closely related to the polynomial time hierarchy . The following applies:

${\ displaystyle \ Sigma _ {i} ^ {p} = \ bigcup _ {k \ in \ mathbb {N}} \ Sigma _ {i} TIME (n ^ {k})}$
${\ displaystyle \ Pi _ {i} ^ {p} = \ bigcup _ {k \ in \ mathbb {N}} \ Pi _ {i} TIME (n ^ {k})}$

credentials

AK Chandra, DC Kozen, LJ Stockmeyer: Alternation. In: Journal of the ACM. Volume 28, Issue 1, 1981, pp. 114-133.
Alternation. In: Christos Papadimitriou: Computational Complexity . 1st edition. Addison-Wesley, 1993, ISBN 0-201-53082-1 , pp. Chapter 16.2, pp. 399-401 .

Individual evidence

↑ Barak, Boaz .: Computational complexity: a modern approach . Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4 , pp. 99–100 ( Draft [PDF; accessed August 31, 2020]).

[1] Barak, Boaz .: Computational complexity: a modern approach . Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4 , pp. 99–100 ( Draft [PDF; accessed August 31, 2020]).