Geodesic
Polynomial Computability of Certain Rudimentary Predicates
Matematičeskie zametki, Tome 74 (2003) no. 1, pp. 69-75 
S. S. Marchenkov. Polynomial Computability of Certain Rudimentary Predicates. Matematičeskie zametki, Tome 74 (2003) no. 1, pp. 69-75. http://geodesic.mathdoc.fr/item/MZM_2003_74_1_a7/
@article{MZM_2003_74_1_a7,
     author = {S. S. Marchenkov},
     title = {Polynomial {Computability} of {Certain} {Rudimentary} {Predicates}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {69--75},
     year = {2003},
     volume = {74},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2003_74_1_a7/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - Polynomial Computability of Certain Rudimentary Predicates
JO  - Matematičeskie zametki
PY  - 2003
SP  - 69
EP  - 75
VL  - 74
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MZM_2003_74_1_a7/
LA  - ru
ID  - MZM_2003_74_1_a7
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T Polynomial Computability of Certain Rudimentary Predicates
%J Matematičeskie zametki
%D 2003
%P 69-75
%V 74
%N 1
%U http://geodesic.mathdoc.fr/item/MZM_2003_74_1_a7/
%G ru
%F MZM_2003_74_1_a7

Voir la notice de l'article provenant de la source Math-Net.Ru

The class of rudimentary predicates is defined as the smallest class of numerical predicates that contains the equality and concatenation predicates and is closed under the operations of propositional logic, explicit transformations, and bounded quantification. Two classes of rudimentary predicates are considered. The first of them consists of the predicates whose prenex normal form of a special type has the quantifier prefix of the form $\exists\forall$. Predicates of the second class can have an arbitrary quantifier prefix, but restrictions are imposed on the Skolem deciding functions. It is proved that any predicate from each of these classes can be computed by a suitable deterministic algorithm in polynomial time.

[1] Kuznetsov A. V., “K teoreme o kanonicheskoi forme dlya ordinalnorekursivnykh funktsii”, Gudstein R. L., Matematicheskaya logika, IL, M., 1961, 149–154

[2] Smalyan R., Teoriya formalnykh sistem, Nauka, M., 1981

[3] Nepomnyaschii V. A., “Rudimentarnye predikaty i tyuringovy vychisleniya”, Dokl. AN SSSR, 195:2 (1970), 282–284 | MR | Zbl

[4] Nepomnyaschii V. A., “Rudimentarnaya interpretatsiya dvulentochnykh tyuringovykh vychislenii”, Kibernetika, 1970, no. 2, 29–35 | Zbl

[5] Nepomnyaschii V. A., “Rudimentarnoe modelirovanie nedeterminirovannykh tyuringovykh vychislenii”, Kibernetika, 1973, no. 2, 23–29 | Zbl

[6] Kosovskii N. K., Elementy matematicheskoi logiki i ee prilozheniya k teorii subrekursivnykh algoritmov, Iz-vo Leningradskogo un-ta, Leningrad, 1981 | Zbl

[7] Marchenkov S. S., “O slozhnosti vychisleniya rudimentarnykh predikatov”, Diskretnaya matem., 12:4 (2000), 83–98 | MR | Zbl

[8] Ershov Yu. L., Palyutin E. A., Matematicheskaya logika, Nauka, M., 1979