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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@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
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/

[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