2021/11/08 by Ziyuan Gao, Gao, Ziyuan, Sanjay Jain +7
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2111.04254
openalex publication_date 2021/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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^* n + O(1) steps. On the other hand, if all problems in P can be solved by an AARM in O(log^*n) rounds, then P ⊂ 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^*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.