# Relationship of algorithm complexity and automata class

I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm. For example is there a range of complexity push down automata can express? If the answer is yes to said question is there a resource depicting the relationship? Thanks!

• "class of automata that can implement the algorithm" -- out of which set? There'll usually not be a single type. Also, google "complexity zoo". – Raphael Feb 6 '16 at 13:30

Yes, there are relationships in many cases!

For example, it is known that any language which is accepted by reversal-bounded counter machines are in $P$ (see here).

Similarly, we know that all regular languages are in $P$, since there's a polynomial time algorithm for determining if an NFA accepts a given word.

There are too many to enumerate here, but in general, more limited computation models are in easier complexity classes.

• Also, context free languages are in P (CYK algorithm) – vonbrand Feb 8 '16 at 2:04

Here are some known results:

1. $\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, where $\mathsf{REG}$ is the set of regular languages. For proofs, see the Wikipedia page on $\mathsf{DSPACE}$.

2. $\mathsf{DCFL} \subseteq \mathsf{SC}$, where $\mathsf{DCFL}$ is the set of deterministic context-free languages, and $\mathsf{SC}$ is Steve's class. See the Wikipedia page on $\mathsf{DCFL}$.

3. $\mathsf{NL} \subseteq \mathsf{LOGCFL} \subseteq \mathsf{AC^1}$, where $\mathsf{LOGCFL}$ is the set of languages logspace-reducible to a context-free language. See the Wikipedia page on $\mathsf{LOGCFL}$, which also gives some languages complete for $\mathsf{LOGCFL}$ under logspace reductions.

4. $\mathsf{CSL} = \mathsf{NSPACE}(n)$, where $\mathsf{CSL}$ is the set of context-sensitive languages. See the Wikipedia page on $\mathsf{CSL}$.

5. The class of languages accepted by deterministic nonerasing PDAs is $\mathsf{DSPACE(n\log n)}$, and the class of languages accepted by non-deterministic nonerasing PDAs is $\mathsf{NSPACE}(n^2)$. See the Wikipedia page on PDAs.

6. Two-stack automata are equivalent in power to Turing machines, but restricting the automata results in weaker models. See a technical report of San Pietro.

Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm.

The question which class of automata can implement a given algorithm like quick sort is tricky, because it is unclear what would count as an implementation of that algorithm. For quick sort, the performed comparisons should certainly be the same, but must the order in which the comparisons occur also be the same? What about the order of read accesses to specific elements of the input? The order of copy, move and swap operations for specific elements?

You would have to specify quite a number of oracles for those operations which matter to you, but then you are already in a very specific situation based on the algorithm, and quite far from the general classes of automata commonly studies. The way around this dilemma is to talk about problems instead of algorithms, and formalize problems by talking about languages.

For example is there a range of complexity push down automata can express?

Not really, because a push down automata can read its input only once and only in forward direction. However, if you split the machine into a part which is allowed to read the input forward and backward as it wishes, and maintain a finite number of pointers to specific input positions (NL), and a part which is a push down automata that receives its input from the other part, then you get the complexity class LOGCFL, which is equal to SAC1 (a circuit class).

If you don't separate those two parts and just add a stack to NL, then you get the automata class AuxPDA, which is equal to the complexity class P. But if you decide to limit the runtime of that automata (with stack and logarithmic auxiliary storage) to polynomial time, then you get NAuxPDAP, which is again equal to LOGCFL. (And if you insist on deterministic polynomial runtime, scrap the stack, but allow polylogarithmic auxiliary storage, then you get SC.)

On the other hand, if you keep the restriction that the automata can read its input only once and only in forward direction, and additionally require that it can use its stack only in a very deterministic way directly based on the input (i.e. the input symbol determines whether that automata pushes something on the stack, pops something from the stack, or leaves the stack untouched), then you end up with a visibly pushdown automata, which recognizes exactly the nested word languages, which can also be recognized in deterministic logarithmic space.