Geodesic
On relationships between complexity classes of Turing machines
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 4, pp. 730-743 
V. N. Zakharov; V. A. Kozmidiadi. On relationships between complexity classes of Turing machines. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 4, pp. 730-743. http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_4_a11/
@article{ZVMMF_2017_57_4_a11,
     author = {V. N. Zakharov and V. A. Kozmidiadi},
     title = {On relationships between complexity classes of {Turing} machines},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {730--743},
     year = {2017},
     volume = {57},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_4_a11/}
}
TY  - JOUR
AU  - V. N. Zakharov
AU  - V. A. Kozmidiadi
TI  - On relationships between complexity classes of Turing machines
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2017
SP  - 730
EP  - 743
VL  - 57
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_4_a11/
LA  - ru
ID  - ZVMMF_2017_57_4_a11
ER  - 
%0 Journal Article
%A V. N. Zakharov
%A V. A. Kozmidiadi
%T On relationships between complexity classes of Turing machines
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2017
%P 730-743
%V 57
%N 4
%U http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_4_a11/
%G ru
%F ZVMMF_2017_57_4_a11

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

Classes of time and space complexity of Turing machines are defined, and relationships between them are discussed. New relationships between the defined complexity classes are described.

[1] Cook S. A., “The complexity of theorem proving procedures”, Proc. the 3rd ACM Simposium on Theory of Comput., 1971, 151–158 | Zbl

[2] Levin L. A., “Universalnye zadachi perebora”, Probl. peredachi informatsii, 9:3 (1973), 115–116 | Zbl

[3] Cook S. A., The P versus NP Problem, (data obrascheniya: 06.06.2014) http://www.claymath.org/sites/default/files/pvsnp.pdf

[4] Lektsiya: Klass NP: svodimost i polnota, , Internet-Universitet Informatsionnykh Tekhnologii http://www.INTUIT.ru

[5] Khartmanis Dzh., Stirnz R., “O vychislitelnoi slozhnosti algoritmov”, Kiberneticheskii sbornik (novaya seriya), 4, Mir, M., 1967, 57–85 | Zbl

[6] Seiferas J., Fischer M., Meyer A., “Separating nondeterministic time complexity classes”, J. ACM, 25 (1978), 146–167 | DOI | MR | Zbl

[7] Paul W. J., Pippenger N., Szemeredi E., Trotter W. T., “On determinism versus nondeterminism and related problems”, Proc. IEEE FOCS'83, 1983, 429–438

[8] Karp R. M., “Reducibility among combinatorial problems”, Complexity of Computer Computations, Symposium Proceedings, eds. R. E. Miller, J. W. Thatcher, J. D. Bohlinger, Plenum Press, N.Y., 1972, 85–103 | DOI | MR

[9] Ladner R., “On the structure of polynomial time reducibility”, J. ACM, 22:1 (1975), 155–171 | DOI | MR | Zbl

[10] Hartmanis J., Lewis P. L. II, Stearns R. E., “Hierarchies of memory-limited computations”, Proc. 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design, 1965, 179–190

[11] Savitch W. J., “Relationships between nondeterministic and deterministic tape complexities”, J. Computer and System Sci., 4:2 (1970), 177–192 | DOI | MR | Zbl

[12] Aaronson S., (data obrascheniya: 07.01.2014) http://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowingif-one-is-a-subset-of-the-other

[13] Hopcroft J., Paul W., Valiant L., “On time versus space”, J. ACM, 24:2 (1977), 332–337 | DOI | MR | Zbl