Geodesic
Complexity properties of recursively enumerable sets and $sQ$-completeness
Matematičeskie zametki, Tome 62 (1997) no. 3, pp. 425-429.

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

The notions of effectively subcreative set and strongly effectively acceleratable set are introduced. It is proved that the notions of effectively subcreative set, strongly effectively acceleratable set, and $sQ$-complete recursively enumerable set are equivalent. 
@article{MZM_1997_62_3_a10,
     author = {R. Sh. Omanadze},
     title = {Complexity properties of recursively enumerable sets and $sQ$-completeness},
     journal = {Matemati\v{c}eskie zametki},
     pages = {425--429},
     publisher = {mathdoc},
     volume = {62},
     number = {3},
     year = {1997},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1997_62_3_a10/}
}
TY  - JOUR
AU  - R. Sh. Omanadze
TI  - Complexity properties of recursively enumerable sets and $sQ$-completeness
JO  - Matematičeskie zametki
PY  - 1997
SP  - 425
EP  - 429
VL  - 62
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_1997_62_3_a10/
LA  - ru
ID  - MZM_1997_62_3_a10
ER  - 
%0 Journal Article
%A R. Sh. Omanadze
%T Complexity properties of recursively enumerable sets and $sQ$-completeness
%J Matematičeskie zametki
%D 1997
%P 425-429
%V 62
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_1997_62_3_a10/
%G ru
%F MZM_1997_62_3_a10
R. Sh. Omanadze. Complexity properties of recursively enumerable sets and $sQ$-completeness. Matematičeskie zametki, Tome 62 (1997) no. 3, pp. 425-429. http://geodesic.mathdoc.fr/item/MZM_1997_62_3_a10/

[1] Blum M., Marques I., “Complexity properties of recursively enumerable sets”, J. Symbolic Logic, 38:4 (1973), 579–593 | DOI | MR

[2] Gill J. T., Morris P. H., “On subcreative sets and $s$-reducibility”, J. Symbolic Logic, 39:4 (1974), 669–677 | DOI | MR

[3] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

[4] Blum M., “A machine-independent theory of the complexity of recursive functions”, J. Assoc. Comput. Mach., 14 (1967), 322–336 | MR | Zbl

[5] Omanadze R. Sh., “Slozhnostnye svoistva rekursivno perechislimykh mnozhestv i $sQ$-polnye mnozhestva”, Soobsch. AN Gruzii, 146:1 (1992), 9–12 | MR | Zbl

[6] Friedberg R. M., Rogers H., “Reducibility and completeness for sets of integers”, Z. Math. Logik Grundlag. Math., 5 (1959), 117–125 | DOI | MR | Zbl

[7] Bulitko V. K., “O sposobakh kharakterizatsii polnykh mnozhestv”, Izv. AN SSSR. Ser. matem., 55:2 (1991), 227–253 | MR | Zbl