Abstract
A survey is given of some results on the complexity of algorithms and computations published up to 1973.
Similar content being viewed by others
Literature cited
V. N. Agafonov, “Normal sequences and finite automata,” in: Probl. Kibern., No. 20, Nauka, Moscow (1968), pp. 123–129.
V. N. Agafonov, The Complexity of Algorithms and Computations. 2, Novosibirsk State Univ. (1975).
V. N. Agafonov, “The complexity of computing pseudorandom sequences,” Algebra Logika, Seminar,7, No. 2, 4–19 (1968).
Ya. M. Barzdin', “Complexity and accuracy of solving initial fragments of the problem of belonging to a recursively enumerable set,” Dokl. Akad. Nauk SSSR,199, No. 2, 262–264 (1971).
Ya. M. Barzdin', “The complexity of programs recognizing whether quantities not exceeding natural numbers belong to a recursively enumerable set,” Dokl. Akad. Nauk SSSR,182, No`. 6, 1249–1252 (1968).
Ya. M. Barzdin', “The complexity of recognizing symmetry on Turing machines,” in: Probl. Kibern., No. 15, Nauka, Moscow (1965), pp. 245–248.
Yu. Ya. Breitbart, “On automatic and ‘zone’ complexity of the predicate ‘be the power of a number’,” Dokl. Akad. Nauk SSSR,196, No. 1, 16–19 (1971).
Yu. A. Bukhshtab, “The realizability of functions on one-dimensional iterative circuits in real time,” in: Probl. Kibern., No. 22, Nauka, Moscow (1970), pp. 85–94.
M. K. Valiev, “Some estimates of computation time for Turing machines with input,” Kibernetika, No. 6, 26–32 (1970).
A. V. Gladkii and A. Ya. Dikovskii, “The theory of formal grammars,” Teor. Veroyatn. Mat. Statistika. Teor. Kibern., Vol. 7 (Itogi Nauki i Tekh.) (1972), pp. 107–142.
V. G. Zharov, “On estimating the complexity of terms of constructive sequences of normal algorithms,” Dokl. Akad. Nauk SSSR,203, No. 4, 746–748 (1972).
I. D. Zaslavskii, “On the pseudofunctions of Shannon,” Zap. Nauchn. Sem. Leningr. Otd. Mat.Inst. Akad. Nauk SSSR,16, 65–76 (1969).
A. K. Zvonkin and L. A. Levin, “The complexity of finite objects and the foundation of the concepts of information and randomness by means of the theory of algorithms,” Usp. Mat. Nauk,25, No. 6, 86–127 (1970).
Ya. B. Kazanovich, “Classification of primitively recursive functions by means of Turing machines,” in: Probl. Kibern., No. 22, Nauka, Moscow (1970), pp. 95–106.
M. I. Kanovich, “On the domains of optimal algorithms,” Dokl. Akad. Nauk SSSR,198, No. 2, 283–285 (1971).
M. I. Kanovich, “On the universality of strongly nonsolvable sets,” Dokl. Akad. Nauk SSSR,204, No. 3, 533–535 (1972).
M. I. Kanovich, “On the complexity of minimizing Boolean functions,” Dokl. Akad. Nauk SSSR,198, No. 1, 35–38 (1971).
M. I. Kanovich, “On the complexity of the resolution of algorithms,” Dokl. Akad. Nauk SSSR,186, No. 5, 1008–1009 (1969).
M. I. Kanovich, “On the complexity of enumerating and resolving predicates,” Dokl. Akad. Nauk SSSR,190, No. 1, 23–26 (1970).
M. I. Kanovich, “The complexity of bounded resolution of semienumerable sets,” Dokl. Akad. Nauk SSSR,203, No. 6, 1246–1248 (1972).
M. I. Kanovich, “The complexity of resolving an enumerable set as a criterion of its universality,” Dokl. Akad. Nauk SSSR,194, No. 3, 500–503 (1970).
M. I. Kanovich and B. A. Kushner, “On an estimate of the complexity of some mass problems of analysis,” Zap. Nauchn. Sem. Leningr. Otd. Mat. Inst. Akad. Nauk SSSR,16, 81–90 (1969).
M. I. Kanovich and N. V. Petri, “Some theorems on the complexity of normal algorithms and computations,” Dokl. Akad. Nauk SSSR,184, No. 6, 1275–1276 (1969).
A. A. Karatsuba and Yu. P. Ofman, “Multiplication of multidigit numbers on automata,” Dokl. Akad. Nauk SSSR,145, No. 2, 293–294 (1962).
B. M. Kloss, “On the definition of the complexity of algorithms,” Dokl. Akad. Nauk SSSR,157, No. 1, 38–40 (1964).
V. A. Kozmidiadi, “On a generalization of finite automata which forms a hierarchy analogous to the classification of A. Grzegorczyk of primitively recursive functions,” in: Probl. Kibern., No. 23, Nauka, Moscow (1970), pp. 127–170.
V. A. Kozmidiadi and S. S. Marchenkov, “On multihead automata,” in: Probl. Kibern., No. 21, Nauka, Moscow (1969), pp. 127–158.
A. N. Kolmogorov, “Three approaches to the definition of the concept of the ‘quantity of information’,” Probl. Peredachi Inf.,1, No. 1, 3–11 (1965).
Yu. A. Kryukov, “Turing machines with two symbols and two states,” Algebra Logika. Seminar,6, No. 3, 51–60 (1967).
Yu. A. Kryukov, “Turing machines with three states and two symbols and one state and symbols,” Kibernetika, No. 1, 12–13 (1971).
A. V. Kuznetsov, “On a theorem on the canonical form for ordinal recursive functions,” Appendix to the book of R. L. Goodstein, Mathematical Logic [Russian translation], IL, Moscow (1961), pp. 149–154.
V. A. Kuz'min, “Realization of functions of a logic algebra by automata, normal algorithms, and Turing machines,” in: Probl. Kibern., No. 13, Nauka, Moscow (1955), pp. 75–96.
G. B. Marandzhyan, “The hierarchy of recursive functions and asymptotic optimality,” Aikakan SSR Gitutyunneri Akademia, Zekuitsner. Dokl. Akad. Nauk ArmSSR,48, No. 4, 193–197 (1969).
G. B. Marandzhyan, “On some properties of asymptotical optimal recursive functions,” Aikakan SSR Gitutyunneri Akademiai Tegekagir. Matematika, Izv. Akad. Nauk ArmSSR, Mat.,4, No. 1, 3–22 (1969).
G. B. Marandzhyan, “On strictly effective immunity of the stems of additively optimal recursive functions,” Aikakan SSR Gitutyunneri Akademia Tegekagir. Matematika, Izv. Akad. Nauk ArmSSR,7, No. 6, 391–398 (1972).
A. A. Markov, “On normal algorithms computing Boolean functions,” Dokl. Akad. Nauk SSSR,157, No. 2, 262–264 (1964).
A. A. Markov, “On normal algorithms connected with the computation of Boolean functions,” Izv. Akad. Nauk SSSR, Ser. Mat.,31, No. 1, 161–208 (1967).
P. Martin-Löf, “On the concept of a random sequence,” Teor. Veroyatn. Ee Primen.,11, No, 2, 198–202 (1966).
S. S. Marchenkov, “On bounded recursions,” Math. Balkan.,2, 124–142 (1972).
S. G. Matveeva, “On the theorem of Rabin on the complexity of computable functions,” Sib. Mat. Zh.,4, No. 3, 546–555 (1965).
Yu. V. Matiyasevich, “On the recognizing in real time of the relation of containment,” Zap. Nauchn. Sem. Leningr. Otd. Mat. Inst. Akad. Nauk SSSR,20, 104–114 (1971).
V. A. Moshchenskii, “On the question of the complexity of Turing computations,” Dokl. Akad. Nauk BSSR,13, No. 10, 871–878 (1969).
V. A. Moshchenskii, “On the estimate of certain functions characterizing the work of Turing machines,” Kibernetika, No. 1, 34–40 (1971).
V. A. Nepomnyashchii, “On a basis for recursively enumerable sets,” Dokl. Akad. Nauk SSSR,170, No. 6, 1262–1264 (1966).
V. A. Nepomnyashchii, “A rudimentary interpretation of two-tape Turing computations,” Kibernetika, No. 2, 29–35 (1970).
V. A. Nepomnyashchii, “Rudimentary predicates and Turing computations,” Dokl. Akad. Nauk SSSR,195, No. 2, 282–284 (1970).
E. S. Orlovskii, “Some questions of the theory of algorithms,” Tr. Mat. Inst. Akad. Nauk SSSR,52, 140–171 (1958).
D. A. Ostroukhov, “On the coding of natural numbers by schemes of normal algorithms,” Z. Math. Log. Grundl. Math.,16, No. 4, 347–352 (1970).
D. A. Ostroukhov, “On an estimate of the complexity of normal algorithms,” Dokl. Akad. Nauk SSSR,184, No. 6, 1292–1293 (1969).
N. V. Petri, “On algorithms connected with predicates and Boolean functions,” Dokl. Akad. Nauk SSSR,185, No. 1, 37–39 (1969).
N. V. Petri, “Complexity of algorithms and their working time,” Dokl. Akad. Nauk SSSR,186, No, 1, 30–31 (1969).
D. Skordev, “Some simple examples of universal functions,” Dokl. Akad. Nauk SSSR,190, No. 1, 45–46 (1970).
N. P. Ter-Zakharyan, “On some quantitative characteristics of algorithmic languages,” Dokl. Akad. Nauk SSSR,190, No. 3, 538–540 (1970).
A. L. Toom, “On the complexity of a scheme of functional elements realizing the multiplication of whole numbers,” Dokl. Akad. Nauk SSSR,150, No. 3, 496–498 (1963).
B. A. Trakhtenbrot, “On normalized signalings for Turing computations,” Algebra Logika. Seminar,5, No. 6, 61–70 (1966).
B. A. Trakhtenbrot, “Optimal computations and the frequency phenomenon of Yablonskii,” Algebra Logika. Seminar,4, No. 5, 79–93 (1965).
B. A. Trakhtenbrot, Complexity of Algorithms and Computations [in Russian], Novosibirsk State Univ. (1967).
B. A. Trakhtenbrot, “Turing computations with logarithmic delay,” Algebra Logika. Seminar,3, No. 4, 33–48 (1964).
R. V. Freivald, “On the order of growth of precise time signalings for Turing computations,” Algebra Logika. Seminar,5, No. 5, 85–93 (1966).
R. V. Freivald, “The complexity of symmetry recognition on Turing machines with input,” Algebra Logika. Seminar,4, No. 1, 47–58 (1965).
V. I. Khomich, “On the complexity of algorithms connected with the realization of logical-arithmetic and propositional formulas,” Dokl. Akad. Nauk SSSR,191, No. 5, 1004–1006 (1970).
G. S. Tseitin, “A lower bound for the number of steps for an inverting normal algorithm and two analogous algorithms,” Zap. Nauch. Sem. Leningr. Otd. Mat. Inst. Akad. Nauk SSSR,20, 243–262 (1971).
G. S. Tseitin, “An estimate of the number of steps in applying a normal algorithm,” Mathematics in the USSR after Forty Years, Moscow,1, 44–45 (1959).
S. Aanderaa and P. C. Fischer, “The solvability of halting problem for 2-state Post machines,” J. Assoc. Comput. Mach.,14, No. 4, 677–682 (1967).
M. A. Arbib, Speed-Up Theorems and Incompleteness Theorems in Automata Theory, Academic Press, New York-London (1966), pp. 6–24.
M. A. Arbib and M. Blum, “Machine dependence of degrees of difficulty,” Proc. Am. Math. Soc.,16, No. 3, 442–447 (1965).
A. J. Atrubin, “A one-dimensional real-time iterative multiplier,” IEEE Trans. Electron. Comput.,14, No. 3, 394–399 (1965).
G. Ausiello, “Abstract computational complexity and cyclic function,” Conf. Rec. of Second Annual ACM Symposium on Theory of Computing,4, 1–47 (1970).
P. Axt, “Enumeration and Grzegorczyk hierarchy,” Z. Math. Logik Grundl. Math.,9, No. 1, 53–65 (1963).
P. Axt, “Iteration of primitive recursion,” Z. Math. Logik Grundl. Math.,11, No. 3, 253–255 (1965).
P. Axt, “Note on the 3-recursive functions,” Z. Math. Logik Grundl. Math.,7, No. 2, 97–98 (1961).
J. Becvar, “Probleme der Komplexität in der Theorie der Algorithmen und Automaten,” Int. Ser. Number. Math. 6, Basel-Stuttgart, 142–157 (1967).
J. Becvar, “Programmkomplexität von borechenbaren Funktionen,” Z. Angew. Math. Mech.,50, Sonderh, 1–4, 82 (1970).
J. Becvar, “Programmkomplexität von Funktionen und Mengen,” Ber. Math. Forschunginst. Oberwolfach, No. 3, 317–326 (1970).
J. Becvar, “Real-time and complexity problems in automata theory,” Kybernetika,1, No. 6, 475–498 (1965).
M. Blum, “A machine-independent theory of the complexity of recursive functions,” J. Assoc. Comput. Mach.,14, No. 2, 322–326 (1967).
M. Blum, “Measures on the computational speed of partial recursive functions,” Q. Progr. Report, 72, Res. Lab. Electronics, MIT, 237–253 (1964).
M. Blum, “On effective procedures for speeding up algorithms,” J. Assoc. Comput. Mach.,18, No. 2, 290–305 (1971).
M. Blum, “On the size of machines,” Inf. Control,11, No. 3, 257–265 (1968).
M. Blum, “Recursive function theory and speed of computation,” Can. Math. Bull.,9, No. 6, 745–750 (1966).
R. V. Book and S. A. Greibach, “Quasi-realtime languages,” Math. Syst. Theory,4, No. 2, 97–111 (1970).
C. Böhm, “A three-tape, three-state, three-symbol universal Turing machine,” Pubbl. Inst. Applic. Calcolo, No. 698 (1968).
A. Borodin, “Computational complexity and the existence of complexity gaps,” J. Assoc. Comput. Mach.,19, 158–174 (1972).
A. Borodin, “Computational complexity 2 A survey,” Proc. Fourth Ann. Princeton Conf. on Information Sci. and Systems, 257–262 (1970).
A. Borodin, R. L. Constable, and J. E. Hopcroft, “Dense and nondense families of complexity classes,” IEEE Conf. Rec. 10th Annual Sympos. Switch. and Automata Theory, Waterloo, 1969, New York, 7–19 (1969).
J. Bulnes, “On the speed of addition and multiplication on one-tape, off-line Turing machines,” Inf. Control,20, No. 5, 415–431 (1972).
W. A. Burkhard, “Complexity problems in real time computation,” Conf. Rec. of Second Ann. ACM Symposium on Theory of Computing, 62–69 (1970).
W. A. Burkhard and P. P. Varaiya, “Complexity problems in real time languages,” Inf. Sci.,3, No. 1, 87–100 (1971).
J. R. Buchi, “Weak second-order arithmetic and finite automata,” Z. Math. Logik Grundl. Math.,6, No. 1, 66–92 (1960).
G. J. Chaitin, “On the length of programs for computing finite binary sequences,” J. Assoc. Comput. Mach.,13, 547–569 (1966).
T. S. Chow, “On the structure of Blum measure,” AFIPS Conf. Proc, Vol. 40, Spring Joint Comput. Conf., Atlantic City, N.J., 1972, Montvale, New Jersey, 503–506 (1972).
J. P. Cleave, “A hierarchy of primitive recursive functions,” Z. Math. Logik Grundl. Math.,9, No. 4, 331–346 (1963).
A. Cobham, “The intrinsic computational difficulty of functions,” Logic, Methodol. Philos. Sci., Amsterdam, 24–30 (1965).
A. Cobham, “Time and memory capacity bounds for machines which recognize squares of palindroms,” IBM Res. Report RC 1621 (1966).
“Complexity of computer computations,” Panel Discussion, Complexity Comput. Computat., Proc. Symp., Yorktown Heights, New York, 1972, New York-London, 169–185 (1972).
R. L. Constable, “On the size of programs in subrecursive formalisms,” Ann. ACM. Symp. Theory Comput., 1–9 (1970).
R. L. Constable, “Two types of hierarchy theorems for axiomatic complexity classes,” Courant. Comput. Sci. Symp. J. Comput., Complex., 1971, New York, New York, 37–63 (1973).
R. L. Constable, “Upward and downward diagonalisation over axiomatic complexity classes,” Technical Report 69-32, Dept. of Computer Science, Cornell University (1969).
R. L. Constable and A. Borodin, “On the efficiency of programs in subrecursive formalisms.” Incomplete version, Extend. Abstr. IEEE Conf. Rec. 11th Annual Symp. Switch. and Automata Theory, Santa Monica, Calif., 1970, New York, New York (1970).
R. L. Constable and J. Hartmanis, “Complexity of formal translations and speed-up results,” Conf. Rec. 3rd Annu. ACM Symp. Theory Comput., Shaker Heights, Ohio, 1971, New York, New York (1971).
S. A. Cook, “Characterizations of pushdown machines in terms of time-bounded computers,” J. Assoc. Comput. Mach.,18, No. 1, 4–18 (1971).
S. A. Cook, “The complexity of theorem-proving procedures,” Conf. Rec. 3rd Annu. ACM Symp. Theory Comput., Shaker Heights, Ohio, 1971, New York, New York (1971).
S. A. Cook and S. O. Aanderaa, “On the minimum computation time of functions,” Trans. Am. Math. Soc.,142, 291–314 (1969).
H. B. Enderton, “Degrees of computational complexity,” J. Comput. Syst. Sci.,6, No. 5, 389–396 (1972).
S. Feferman, “Classifications of recursive functions by means of hierarchies,” Trans. Am. Math. Soc.,104, No. 1, 101–122 (1962).
P. C. Fischer, “The reduction of tape reversals for off-line one-tape Turing machines,” J. Comput. Syst. Sci.,2, No. 2, 136–147 (1968).
P. C. Fischer, “Turing machines with a schedule to keep,” Inf. Control,11, Nos. 1–2, 138–146 (1967).
P. C. Fischer, J. Hartmanis, and M. Blum, “Tape reversal complexity hierarchies,” IEEE Conf. Rec. of 1968 Ninth Annual Symp. on Switching and Automata Theory, 373–382 (1968).
P. C. Fischer, A. R. Meyer, and A. L. Rosenberg, “Counter machines and counter languages,” Math. Syst. Theory,2, No. 3, 265–283 (1968).
P. C. Fischer, A. R. Meyer, and A. L. Rosenberg, “Real time simulation of multihead tape units,” J. Assoc. Comput. Mach.,19, No. 4, 590–607 (1972).
P. C. Fischer, A. R. Meyer, and A. L. Rosenberg, “Time-restricted sequence generation,” J. Comput. Syst. Sci.,4, No. 1, 50–73 (1970).
E. P. Glinert, “On restricted Turing computability,” Math. Syst. Theory,5, No. 4, 331–343 (1971).
A. Grzegorczyk, “Some classes of recursive functions,” Instytut Matematyczny Polskiej Akademii Nauk. Rozprawy Matematyczne, 4 (1953).
J. Hartmanis, “Computational complexity of one tape Turing machine computations,” J. Assoc. Comput. Mach.,15, No. 2, 325–339 (1968).
J. Hartmanis, “On the complexity of undecidable problems on automata theory,” J. Assoc. Comput. Mach.,16, No. 1, 160–167 (1969).
J. Hartmanis, “Size argument in the study of computation speeds,” Proc. Symp. Comput. and Automata, New York, New York, 1971, Brooklyn, New York (1971).
J. Hartmanis, “Tape reversal bounded Turing machine computations,” J. Comput. Syst. Sci.,2, No. 2, 117–135 (1968).
J. Hartmanis and J. E. Hopcroft, “An overview of the theory of computational complexity,” J. Assoc. Comput. Mach.,18, No. 3, 444–475 (1971).
J. Hartmanis, P. M. Lewis II, and R. E. Stearns, “Classifications of computations by time and memory requirements,” Proc. of IFIP Congress I, Washington, D. C. (1965).
J. Hartmanis and H. Shank, “Two memory bounds for the recognition of primes by automata,” Math. Syst. Theory,3, No. 2, 125–129 (1969).
J. Hartmanis and R. E. Stearns, “Automata-based computational complexity,” Inf. Sci.,1, No. 2, 173–184 (1969).
J. Hartmanis and R. E. Stearns, “On the computational complexity of algorithms,” Trans. Am. Math. Soc.,117, No. 5, 285–306 (1965).
I. M. Havel, “Weak complexity measures,” SIGACT News,8, 21–30 (1971).
J. P. Helm and P. R. Young, “On size vs efficiency for programs admitting speed-ups,” J. Symbol. Log.,36, No. 1, 21–27 (1971).
F. C. Hennie, “Crossing sequences and off-line Turing machine computations,” IEEE Conf. Rec. Switch. Circuit. Theory and Logic Design, Ann Arbor, Mich., 1965, New York, New York, Inst. Electr. and Electron Engrs. Inc. (1965).
F. C. Hennie, “One-tape, off-line Turing machine computations,” Inf. Control,8, 553–578 (1965).
F. C. Hennie, “On-line Turing machine computations,” IEEE Trans. Electron. Comput.,15, No. 1, 35–44 (1966).
F. C. Hennie and R. E. Stearns, “Two-tape simulation of multitape Turing machines,” J. Assoc. Comput. Mach.,13, No. 4, 533–546 (1976).
G. T. Herman, “A new hierarchy of elementary functions,” Proc. Am. Mach. Soc.,20, No. 2, 557–562 (1969).
G. T. Herman, “The equivalence of different hierarchies of elementary functions,” Z. Math. Log. Grundl.,17, No. 3, 219–224 (1971).
G. T. Herman, “The halting problem of one state Turing machines with n-dimensional tape,” Z. Math. Logik Grundl. Math.,14, No. 2, 185–191 (1968).
P. K. Hooper, “Some small, multitape universal Turing machines,” Inf. Sci.,1, No. 2, 209–215 (1969).
J. E. Hopcroft and J. D. Ullman, “Relation between time and tape complexities,” J. Assoc. Comput. Mach.,15, No. 3, 414–427 (1968).
J. E. Hopcroft and J. D. Ullman, “Some results on tape-bounded Turing machines,” J. Assoc. Comput. Mach.,16, No. 1, 168–177 (1969).
O. H. Ibarra, “A note concerning nondeterministic tape complexities,” J. Assoc. Comput. Mach.,18, No. 4, 608–612 (1972).
L. Kalmar, “Eguszerü pelda eldönthetetlen aritmetikai problemara” (Ein einfaches Beispiel für ein unentscheibares arithmetisches Problem), Matematikai es Fizikai Lapok,50, 1–23 (1943).
T. Kameda, “Constant-tape-reversal bounded nondeterministic Turing machine computations,” Comput. Symp., 1970, Bonn, Proc., Frankfurt (1973).
T. Kameda and K. Vollmar, “Note on tape reversal complexity of languages,” Inf. Control,17, No. 2, 203–215 (1970).
T. Kameda and R. Vollmar, “Zur Umkehrkomplexität von Sprachen,” Ber. Math. Forschungsinst. Oberwolfach,3, 327–339 (1970).
R. M. Karp, “Reducibility among combinatorial problems,” Complexity Comput. Computat., Proc. Symp., Yorktown Heights, New York, 1972, New York-London (1972).
R. M. Karp, “Some bounds on the storage requirements of sequential machines and Turing machines,” J. Assoc. Comput. Mach.,14, No. 3, 478–489 (1967).
S. C. Kleene, “Extension of an effectively generated class of functions by enumeration,” Colloq. Math.,6, 67–78 (1958).
D. E. Knouth, The Art of Computer Programming, 2, Addison-Wesley (1969).
L. H. Landweber and E. L. Robertson, “Recursive properties of abstract complexity classes,” J. Assoc. Comput. Mach.,19, No. 2, 296–308 (1972).
E. L. Lawler, “The complexity of combinatorial computations, a survey,” Proc. Symp. Comput. and Automata, New York, New York, 305–311 (1971).
F. D. Lewis, “The enumerability and invariance of complexity classes,” J. Comput. Syst. Sci.,5, No. 3, 286–303 (1971).
G. Longo, “Towards an abstract analysis of time progression of consumption of resources during computation,” Int. Comput. Symp., Venice (1972).
L. Longo, “Axioms for time dependence of resource consumption in computing recursive functions,” SIGACT News,12, 14–24 (1971).
D. W. Loveland, “A variant of the Kolomogorov concept of complexity,” Inf. Control,15, No. 6, 510–526 (1969).
M. H. Löb and S. S. Wainer, “Hierarchies of number-theoretic functions. I,” Arch.Mach. Log. Grundl.,13, Nos. 1–2, 39–51 (1970).
M. H. Löb and S. S. Wainer, “Hierarchies of number-theoretic functions. II,” Arch. Math. Log. Grundl.,13, Nos. 3–4, 97–113 (1970).
N. A. Lynch, “Relativization of the theory of computational complexity,” Proj. MAC Tech. Rept., No. 99 (1972).
P. Martin-Löf, “Complexity oscillations in infinite binary sequences,” Z. Wahrscheinlichkeitstheory Verw. Geb.,19, No. 3, 225–237 (1971).
P. Martin-Löf, “On the notion of randomness,” Intuitionism and proof theory, New York, 73–78 (1968).
P. Martin-Löf, “The definition of random sequences,” Inf. Control,9, No. 6, 602–619 (1966).
E. M. McCreight and A. R. Meyer. “Classes of computable functions defined by bounds on computation: preliminary report,” Conf. Rec. of ACM Symp. on Theory of Computing, 79–88 (1969).
A. R. Meyer, “Program size in restricted programming languages,” Inf. Control,21, No. 4, 382–394 (1972).
A. R. Meyer, “Theories of computational complexity,” Comput. Sci. Res. Review, Carnegie -Mellon Univ., 17–22 (1968).
A. R. Meyer, “Weak monadic second-order theory of successor is not elementary recursive,” Preliminary Report, Cambridge, Mass., 1–24 (1972).
A. R. Meyer and A. Bagchi, “Program size and economy of descriptions,” Preliminary Report, 4th Annual ACM Symp. Theory Comput., Denver, Colo., 183–186 (1972).
A. R. Meyer and P. Fischer, “Economy of descriptions by automata, grammars and formal systems,” Conf. Rec. 12th Annual Symp. Switch. and Automata Theory, East Lansing, Mich., 1971, New York, New York, 188–191 (1971).
A. R. Meyer and P. Fischer, “Computational speed-up by effective operators,” J. Symbol. Log.,37, No. 1, 55–68 (1972).
A. R. Meyer and E. M. McCreight, “Computationally complex and pseudorandom zero-one valued functions,” Theory Mach. Comput., New York-London, 19–42 (1971).
A. R. Meyer and R. Moll, “Honest bounds for complexity classes of recursive functions,” 13th Annual Symp. Switch. and Automata Theory, 1972, New York, New York, 61–66 (1972).
A. R. Meyer, A. L. Rosenberg, and P. C. Fischer, “Turing machines with several read-write heads,” Preliminary Report, IEEE Conf. Rec. 8th Annual Symp. Switch. and Automata Theory, Austin, Texas, 1967, New York, New York, 117–127 (1967).
A. R. Meyer and D. M. Ritchie, “A classification of the recursive functions,” Z. Math. Log. Grundl. Math.,18, No. 1, 71–81 (1972).
M. L. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Englewood Cliffs, New Jersey (1967).
M. L. Minsky, “Size and structure of universal Turing machines using Tag systems,” Recurs. Funct. Theory, Am. Math. Soc., 229–238 (1962).
J. Myhill, “A stumblingblock in constructive mathematics,” Abstract, J. Symbol. Logic,18, 190–191 (1953).
A. Nozaki, “On the notion of universality of Turing machine,” Kybernetika,5, No. 1 (1969).
D. Pager, “On the efficiency of algorithms,” J. Assoc. Comput. Mach.,17, No. 4, 708–714 (1970).
R. A. Di Paola, “Random sets in subrecursive hierarchies,” J. Assoc. Comput. Mach.,16, No. 4, 621–630 (1969).
Ch. Parsons, “Hierarchies of primitive recursive functions,” Z. Math. Logik Grundl. Math.,14, No. 4, 357–376 (1968).
M. S. Paterson, “Tape bounds for time bounded Turing machines,” J. Comput. Syst. Sci.,6, No. 2, 116–124 (1972).
R. Peter, “Mehrfache und transfinite Rekursionen,” J. Symbol. Logic,15, 248–272 (1950).
R. Peter, Rekursive Funktione, Budapest (1951).
R. Peter, “Über die mehrfache rekursion,” Math. Annalen,113, 489–527 (1936).
M. O. Rabin, “Real time computation,” Israel J. Math.,1, No. 4, 203–211 (1963).
M. O. Rabin, “Speed of computation of functions and classification of recursive sets,” Bull. Res. Council Israel,8, No. 1, 69–70 (1959).
R. W. Ritchie, “Classes of predictably computable functions,” Trans. Am. Math. Soc.,106, 139–173 (1963).
R. W. Ritchie, “Classes of recursive functions based on Ackermann's function,” Pac. J. Math.,15, No. 3, 1027–1044 (1965).
E. L. Robertson, “A corrected definition of ‘local speedup’,” SIGACT News,6, 15–16 (1970).
E. L. Robertson, “Complexity classes of partial recursive functions (preliminary version),” Conf. Rec. 3rd Annual ACM Symp. Theory Comput., Shaker Heights, Ohio, 1971, New York, New York, 258–266 (1971).
A. L. Rosenberg, “Real-time definable languages,” J. Assoc. Comput. Mach.,14, No. 4, 645–662 (1967).
N. A. Routledge, “Ordinal recursion,” Proc. Cambridge Philos. Soc.,49, Part 2, 175–182 (1953).
S. S. Ruby and P. C. Fischer, “Translational methods and computational complexity,” IEEE Conf. Rec. Switch. Circuit Theory and Log. Design, Ann Arbor, Mich., 1965, New York, New York, Inst. Electr. and Electron. Eng. Inc., 173–178 (1965).
W. J. Savitch, “Relationships between nondeterministic and deterministic tape complexities,” J. Comput. Syst. Sci.,4, No. 2, 177–192 (1970).
A. Schmitt, “Die Zustands-Komplexitats-Klassen von Turing-machinen,” Ber. Math. Forschungsinst. Oberwolfach, No. 3, 343–350 (1970).
A. Schmitt, “The state complexity of Turing machines,” Inf. Control,17, No. 3, 217–225 (1970).
C. P. Schnorr, “A unified approach to the definition of random sequences,” Math. Syst. Theory,5, No. 3, 246–258 (1971).
C. P. Schnorr, “Eine Bemerkung zum Begriff der zufalligen Folge,” Z. Wahrscheinlichkeitstheor. Verw. Geb.,14, No. 1, 27–35 (1969).
C. P. Schnorr, “Klassifikation der Zufallsgesetze nach Komplexität und Ordnung,” Z. Wahrschienlichkeitstheor. Verw. Geb.,16, No. 1, 1–21 (1971).
C. P. Schnorr, “The process complexity and effective random tests,” 4th Annual ACM Symp. Theory of Comput., Denver, Colo., 1972, S. 1, 168–176 (1972).
C. P. Schnorr, “Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begrundung der Wahrscheinlichkeitstheorie,” Lect. Notes Math.,218, IV (1971).
A. Schönhage, “Multiplikation grosser Zahlen,” Computing (Arch. Elektron. Rechnen),1, 182–196 (1966).
A. Schönhage and V. Strassen, “Schnelle Multiplikation grosser Zahlen,” Computing,7, Nos. 3–4, 281–292 (1971).
H. Schwichtenberg, “Rekursionszahlen und die Grzegorczyk-Hierarchie,” Arch. Math. Logik Grundl.,12, Nos. 1–2, 85–97 (1969).
C. E. Shannon, “A universal Turing machine with two internal states,” Ann. Math. Stud.,34, 157–165 (1959).
T. Skolem, “A theorem on recursively enumerable sets,” Abstr. of Short Comm. Int. Congress Math., Stockholm, 11 (1962).
A. R. Smith, “Real-time language recognition by one-dimensional cellular automata,” J. Comput. Syst. Sci.,6, No. 3, 233–253 (1972).
R. M. Smullyan, Theory of Formal Systems (Ann. Math. Studies, No. 47), Univ. Press, Princeton, New Jersey, XTV (1961).
R. J. Solomonoff, “A formal theory of inductive inference. Part I,” Inf. Control,7, No. 1, 1–22 (1964).
R. E. Stearns, J. Hartmanis, and P. M. Lewis II, “Hierarchies of memory limited computations,” IEEE Conf. Rec. Switch. Circuit Theory and Logic Design, Ann Arbor, Mich, 1965, New York, New York, Inst. Electr. and Electron. Eng., Inc., 179–190 (1965).
L. J. Stockmeyer and A. R. Meyer, “Word problems requiring exponential time,” Preliminary Report, Cambridge, Mass., 1–17 (1972).
H. J. Stoss, “A two-tape simulation of Turing machines,” Computing,7, 222–235 (1971).
H. J. Stoss, “k-band simulation von k-kops Turing machinen,” Computing,6, Nos. 3–4, 309–317 (1970).
P. Strnad, “On-line Turing machine recognition,” Inf. Control,12, 442–452 (1968).
P. Strnad, “O reprezentovatelnosti jiste mnozine slov automatem v realnem case,” Sb. Vedeck. Praci Vysoke Skoly Strojni a Textil, Liberei, 1966, Prague, 23–27 (1966).
D. B. Thompson, “Subrecursiveness: machine-independent notions of computability in restricted time and storage,” Math. Syst. Theory,6, No. 1, 3–15 (1972).
S. S. Wainer, “A classification of the ordinal recursive functions,” Arch. Math. Log. Grundl.,13, Nos. 3–4, 136–153 (1970).
S. S. Wainer, “Ordinal recursion and refinement of the extended Grzegorczyk hierarchy,” J. Symbol. Logic,37, No. 2, 281–292 (1972).
Shigeru Watanabe, “5-symbol 8-state and 5-symbol 6-state universal Turing machines,” J. Assoc. Comput. Machinery,8, No. 4, 476–483 (1961).
S. Winograd, “On the time required to perform addition,” J. Assoc. Comput. Mach.,12, No. 2, 277–285 (1965).
S. Winograd, “On the time required to perform multiplication,” J. Assoc. Comput. Mach.,14, No. 4, 793–802 (1967).
H. Yamada, “Real-time computation and recursive functions not real-time computable,” IRE Trans. Electron. Comput.,11, No. 6, 753–760 (1962).
P. R. Young, “A note on dense and nondense families of complexity classes,” Math. Syst. Theory,5, No. 1, 66–70 (1971).
P. R. Young, “Speed-ups by changing the order in which sets are enumerated,” Math. Syst. Theory,5, 145–156 (1971).
Additional information
Translated from Itogi Nauki i Tekhniki. Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 16, pp. 103–149, 1979.
Rights and permissions
About this article
Cite this article
Marchenkov, S.S., Matrosov, V.L. Complexity of algorithms and computations. J Math Sci 15, 140–165 (1981). https://doi.org/10.1007/BF01084283
Issue Date:
DOI: https://doi.org/10.1007/BF01084283