Alternating Automatic Register Machines

Abstract

This paper introduces and studies a new model of computation called an Alternating Automatic Register Machine (AARM). An AARM possesses the basic features of a conventional register machine and an alternating Turing machine, but can carry out computations using bounded automatic relations in a single step. One finding is that an AARM can recognise some NP-complete problems, including SAT (using a particular coding), in ${\log }^{\ast }n+O(1)$ steps. On the other hand, if all problems in P can be solved by an AARM in $O({\log }^{\ast }n)$ rounds, then $\text{P}\subset \text{PSPACE}$. Furthermore, we study an even more computationally powerful machine, called a Polynomial-Size Padded Alternating Automatic Register Machine (PAARM), which allows the input to be padded with a polynomial-size string. It is shown that the polynomial hierarchy can be characterised as the languages that are recognised by a PAARM in ${\log }^{\ast }n+O(1)$ steps. These results illustrate the power of alternation when combined with computations involving automatic relations, and uncover a finer gradation between known complexity classes.

26 pages, 2 figures

References in corpus (1)

• Three Lectures on Automatic Structures