This article is cited in 1 paper

On the complexity of the computation of rudimentary predicates

S. S. Marchenkov


Abstract: The class of rudimentary predicates is defined as the minimal class of numerical predicates which contains the equality and concatenation predicates and is closed with respect to the propositional logic operations, the explicit transformations, and the bounded quantification. The complexity of computation of rudimentary predicates is defined in terms of alternating Turing machines with a finite number of alternations. Polynomial computability of rudimentary $\exists$- and $\forall$-predicates by deterministic Turing machine is proved. Hierarchies $\{R\Sigma_k\}$ and $\{R\Pi_k\}$ of the rudimentary predicate class are defined. The class $R\Sigma_1\cap R\Pi_1$ is analysed. Unsolvability of the non-emptiness problem for the class $R\Pi_1$ is proved.
The research was supported by the Russian Foundation for Basic Research, grant 00–01–00351.

UDC: 519.712

Received: 30.03.2000

DOI: 10.4213/dm351

 English version: Discrete Mathematics and Applications, 2000, 10:6, 571–585

Bibliographic databases:

• 
•