4.2 Computational Models and Complexity Classes
4.2.2 Alternating Turing Machines
An alternating Turing machine (henceforth ATM) is a generalization of a nondeterminis-tic TM, in an attempt to capture parallelism and logical facts involved in computations.
The ATM model is the parallel version of the TM model. Consequently, an ATM may be logarithmically faster than its counterpart. Intuitively, this is because when passing from a configuration to another, a nondeterministic TM has several options to follow, but only one at a moment, in an “horizontal” computation fashion, while in an ATM the bulk of all possible options (guesses) are considered all at a moment and spawned in a “vertical” fashion. Each bulk of guesses may be handled either by an OR (existential, also denoted by “∨”) or by an AND (universal, also denoted by “∧”) state. Therefore, what is computed in a “left to right” fashion by a sequential TM is computed in a
“top-down” fashion by an ATM, which, at a certain moment, handles several guesses that a sequential TM may perform along a certain “horizontal” path.
Since a sequential nondeterministic TM accepts an input if, starting from an initial configuration, there exists at least one sequence of moves, in an “horizontal” fashion that leads to acceptance, intuitively, each TM configuration, placed on a successful path, must be handled in an ATM by an OR state (OR acceptance corresponds to nondeterministic acceptance). Hence, an ATM with only OR guesses works exactly as a nondeterministic TM (there is no parallelism). What makes an ATM be faster than a sequential TM is the existence of AND states, which intuitively means that up to a certain AND bulk the input is accepted if each guess in this bulk is placed on a successful computation path.
In order to allow acceptance in sublinear time, besides AND states, an ATM must be endowed with random access to its input facility, which leads to the idea of the random access or indexing ATM. Theoretically, (indexing) ATMs are very economical machines.
Unfortunately, (indexing) ATMs are difficult to be implemented by sequential TMs.
However, finding an algorithm that leads to the acceptance of a language by an indexing ATM proves that the corresponding language is efficiently parallelizable, i.e., it is of low complexity. Therefore, the (indexing) ATM model may be considered a bridge between sequential models of computations, and more complex parallel models of computations, such as Boolean or arithmetical circuits, allowing relationships between sequential and parallel complexity classes. Formally, we have [6]
Definition 4.7. Ak-tapealternating Turing machine(ATM) is an 8-tupleM = (Q,Σ,Γ, k, q0, B, δ, g), wherek,k≥1, is the number of read-write working tapes (two-way, semi-infinite),Qis the finiteset of states,g:Q→ {∧,∨, acc, rej}is a function that partitions the states of Qintouniversal (∧), existential(∨),accepting, and rejecting, respectively, Γ and Σ are the finite sets of tape and input alphabets, respectively, q0 is the initial state,B is the blank symbol, whileδ ⊆(Q×Σ×Γk)×(Q×Γk× {lef t, right, stay}k+1) is the transition relation.
Aconfigurationof an ATM consists of a state (universal, existential, accepting or reject-ing), the head position on the read-only, semi-infinite, input tape (which contains the input word delimited at the right by blank symbols), and the positions of the k heads on the working tapes. When passing from a state to another, the ATM reads a symbol from each of the k+ 1 tapes, moves its heads to the left or right, or leaves them in the same position, on their corresponding tapes, and it modifies at most one cell from each working tape. An ATM starts the computation in the initial state q0, with all its working tapes empty, and all its heads placed on the first cell of their respective tapes.
This is what is called the initial configuration.
Chapter 4. Asymptotic Growth, Computational Models, and Complexity Classes
The computation tree associated with an ATM and an input x is a (possibly infinite, if the ATM does not halt) tree whose vertices are the ATM’s configurations, such that the root holds the initial configuration and for any vertex v its children are the immediate successor configurations ofv. The leaves of the computation tree correspond to accepting or rejecting configurations. An input w is accepted if there exists a computation tree of M on w, called accepting computation tree, in which the root is labeled by 1 using the following bottom-up labeling procedure. Each accepting leaf is labeled by 1. Each vertex corresponding to an existential configuration is labeled by 1 if at least one of its children is labeled by 1, and each vertex corresponding to an universal configuration is labeled by 1 if all its children are labeled by 1.
Definition 4.8. An indexing (random-access) ATM is an ATM composed of an input tape, kworking tapes (k≥1), and an index tape. The indexing ATM has k+ 1 heads corresponding to the working tapes and the index tape. There is no need of a head for the input tape, since the indexing ATM reads a symbol from the input tape, through the index tape as follows. It writes an integer i, i ≤ n, in binary, on the index tape, wheren is the length of the input, and enters in a state requiring the symbol placed at theith location on the input tape to be visible to the machine.
From the initial state or a given vertex in the computation tree an (indexing) ATM may proceed either with an universal configuration (of which state is an universal state) or with an existential configuration (of which state is existential). Since an ATM is a non-deterministic machine, there will be one or more such universal or existential configurations placed at the same level of the ATM. All edges going from a certain vertex, in the computation tree, to universal (existential) configurations, placed at the same level of the ATM, are called universal (respectively, existential)branches. When in a universal (existential) branch the ATM performs some more complex operations, such as simulating another ATM, we call the corresponding branch universal (respectively, existential) process.
The main complexity measures of an ATM aretime, i.e., the height of the computation tree of M, space of M, i.e., the maximum of the space used by M on any configu-ration, and alternations i.e., the number of alternations from existential to universal configurations in a computation tree.
Definition 4.9. LetM be an ATM that always halts, and Σ the input alphabet of M.
The function t:N→ Nis the time complexity of M if for any input w∈ Σ∗, of length n, there exits an accepting computation tree of M on wof height at most t(n). In this case, the language L⊆ Σ∗ composed of all words accepted by M is said to be of time complexity t(n). The time complexity classAT IM E(t(n)) is composed of all languages decided by an ATM within O(t(n)) time.
Using universal branches to relate different symbols on the input an indexing ATM can read a string of lengthninO(logn) time. ALOGT IM E is the class of languages recog-nizable by an indexing ATM in logarithmic time, i.e., ALOGT IM E=AT IM E(logn).
AP OLY LOGT IM E = S
k≥1AT IM E(logkn), AP T IM E = S
k≥1AT IM E(nk), while AEXP T IM E=S
k≥1AT IM E(2nk).
Definition 4.10. LetM be an ATM that always halts, and Σ the input alphabet ofM.
The function s:N→Nis the space complexity of M if for any inputw∈Σ∗, of length n, there exits an accepting computation tree of M on w such that the space used on each configuration, on this accepting computation tree, is at mosts(n). In this case, the languageL⊆Σ∗ composed of all words accepted byM is said to be ofspace complexity s(n). Thespace complexity classASP ACE(s(n)) is composed of all languages decided by an ATM by usingO(s(n)) space.
Note that the space used to write an integer in binary, on the index tape of an indexing ATM, is included in the machine space bound. We have the next space complexity classes ALOGSP ACE =ASP ACE(logn), AP OLY LOGSP ACE =S
k≥1ASP ACE(logkn), AP SP ACE =S
k≥1ASP ACE(nk),AEXP SP ACE =S
k≥1ASP ACE(2nk).
Let i ≥ 1. An ATM M is called a Σi-ATM (Πi-ATM) if each accepting computation tree ofM, on any input, has as root an existential configuration (respectively, universal configuration) and at mosti−1 alternations from existential to universal configurations.
The complexity class ΣiT IM E(t(n)) (ΠiT IM E(t(n))) is the set of languages accepted by a Σi-ATM (respectively, by a Πi-ATM) within O(t(n)) time. The complexity class ΣiSP ACE(s(n)) (ΠiSP ACE(s(n))) is the set of languages accepted by a Σi-ATM (re-spectively, by a Πi-ATM) by using O(s(n)) space.
By convention, Σ0T IM E(t(n)) = Π0T IM E(t(n)) =DT IM E(t(n)) and Σ0SP ACE(s(n))
= Π0SP ACE(s(n)) = DSP ACE(s(n)), since a Σ0-ATM and Π0-ATM are considered to be deterministic TMs. On the other hand Σ1T IM E(t(n)) = N T IM E(t(n)) and Σ1SP ACE(s(n)) = N SP ACE(s(n)) since, a Σ1-ATM is exactly a nondeterministic TM (as explained above). As¬∨=∧we have ΠiT IM E(t(n)) =coΣiT IM E(t(n)) and ΠiSP ACE(s(n)) =coΣiSP ACE(s(n)), for eachi≥1, where bycoX={L|L¯ ∈X}, we denote the complement of the classX, where ¯Lis the complement ofL(see Section2.2).
Consequently, ΣP0 =S
k≥0Σ0T IM E(nk) = ΠP0 =S
k≥0Π0T IM E(nk) =P, ΣP1 =S
k≥0Σ1T IM E(nk) =N P, ΠP1 =S
k≥0Π1T IM E(nk) =coN P, ΣL0 = Σ0SP ACE(logn) = ΠL0 = Π0SP ACE(logn) =L, and
ΣL1 = Σ1SP ACE(logn) =N L, ΠL1 = Π1SP ACE(logn) =coN L.
AsN L[114,200]
= coN L, we have ΣL1 = ΠL1. It is an open question whether or not ΣP1= ΠP1,
Chapter 4. Asymptotic Growth, Computational Models, and Complexity Classes
Thepolynomial time alternation hierarchy is defined asP H =S
i≥0ΣPi =S
i≥1ΠPi and the logarithmic space alternation hierarchy is defined as LAH = S
i≥0ΣLi = S
i≥1ΠLi. Since ΣL1 = ΠL1 the LAH hierarchy collapses at the first level, i.e., N L = coN L = LAH. This is because ΣXi = ΠXi , for some i, if and only if ΣXj = ΣXi , for any i < j, where X ∈ {P, L}. In this case it is said that the corresponding alternation hierarchy collapses at the level i. Furthermore, any s(n)-space alternation hierarchy, such that s(n) ≥ logn is a fully space constructible function, collapses at the second level3 [116]. If log logn ≤ s(n) < logn, then Σi−1SP ACE(s(n)) ⊂ ΣiSP ACE(s(n)), Σi−1SP ACE(s(n)) ⊂ ΠiSP ACE(s(n)), Πi−1SP ACE(s(n)) ⊂ ΣiSP ACE(s(n)), and Πi−1SP ACE(s(n)) ⊂ ΠiSP ACE(s(n)), for any i ≥ 2, [18, 83, 133]. Hence, for any functions(n), with log logn≤s(n)<logn, there is an infinite alternating space hierar-chy. Whether or not the P H hierarchy collapses is still an open problem.
We have DT IM E(f(n)) ⊆ N T IM E(f(n)) ⊆ AT IM E(f(n))
Informally, a multicounter (MC) machine is an accepting device composed of a finite state control, an input head, an input tape, and a finite number of semi-infinite storage tapes that function as counters capable to store any integer. If the input head is allowed to move only to the right the machine is aone-way (or on-line)multicounter, otherwise is atwo-way(or off-line) multicountermachine. In this thesis we deal only with on-line MC machines. Formally we have
3An alternative reason is that, for any space constructible function s(n) ≥ logn, we have N SP ACE(s(n)) =coN SP ACE(s(n)).