Paper Info
Title
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 CNF-SAT (using a particular coding), in $$\log ^* n + \mathcal {O}(1)$$ steps. On the other hand, if all problems in P can be solved by an AARM in $$\mathcal {O}(\log ^*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 ^*n + \mathcal {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.
Year
DOI
Venue
2022
10.1007/978-3-031-17715-6_14
Theoretical Aspects of Computing – ICTAC 2022
Keywords
DocType
ISSN
Theory of computation, Computational complexity, Automatic relation, Register machine, Nondeterministic complexity, Alternating complexity, Measures of computation time
Conference
0302-9743
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Ziyuan Gao100.34
Sanjay Jain21647177.87
Zeyong Li300.34
Ammar Fathin Sabili400.34
Frank Stephan521539.36