|
This article is cited in 1 scientific paper (total 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.
Received: 30.03.2000
Citation:
S. S. Marchenkov, “On the complexity of the computation of rudimentary predicates”, Diskr. Mat., 12:4 (2000), 83–98; Discrete Math. Appl., 10:6 (2000), 571–585
Linking options:
https://www.mathnet.ru/eng/dm351https://doi.org/10.4213/dm351 https://www.mathnet.ru/eng/dm/v12/i4/p83
|
Statistics & downloads: |
Abstract page: | 515 | Full-text PDF : | 293 | References: | 52 | First page: | 1 |
|