On the complexity of the computation of rudimentary predicates

S. S. Marchenkov

Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 83-98

Résumé

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.