Complexity of computations

ABSTRACT

The framework for research in the theory of complexity of computations is described, emphasizing the interrelation between seemingly diverse problems and methods. Illustrative examples of practical and theoretical significance are given. Directions for new research are discussed.

REFERENCES

• 1: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• 2: Brent, R,P. On the addition of binary numbers. IEEE Trans. Comptrs. C-19 (1970), 758-759.
• 3: Brent, R.P. The parallel evaluation of algebraic expressions in logarithmic time. Complexity of Sequential and Parallel Numerical Algorithms, J.F. Traub, Ed., Academic Press, New York, 1973, pp. 83-102.
• 4: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 5: Fischer, M.J., and Rabin, M.O. Super-exponential complexity of Presburger arithmetic. In Complexity of Computations (SIAM- AMS Proc., Vol. 7), R.M. Karp Ed., 1974, pp. 27-41.
• 6: Floyd, R.W. Permuting information in idealized two-level storage. In Complexity of Computer Computations, R. Miller and J. Thatcher Eds., Plenum Press, New York, 1972, pp. 105-109.
• 7: Karp, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher Eds., Plenum Press, New York, 1972, pp. 85-103.
• 8: Meyer, A.R. The inherent computational complexity of theories of order. Proc. Int. Cong. Math., Vol. 2, Vancouver, 1974, pp. 477- 482.
• 9: Motzkin, T.S. Evaluation of polynomials and evaluation of rational functions. Bull. Amer. Math. Soc. 61 (1955), 163.
• 10: Munro, I., and Paterson, M. Optimal algorithms for parallel polynomial evaluation. J. Comptr. Syst. Sci., 7 (1973), 189-198.
• 11: M. S. Paterson , M. J. Fischer , A. R. Meyer, AN IMPROVED OVERLAP ARGUMENT FOR ON-LINE MULTIPLICATION, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 12: Presburger, M. Uber die Vollstfindigkeit eines gewissea Systems Arithmetic ganzer Zahlen in welchem die Addition als eiilzige Operation hervortritt. Comptes-rendus du I Congr~s de Mathematiciens de Pays Slaves, Warsaw, 1930, pp. 92-101,395.
• 13: Rabin, M.O. Speed of computation and classification of recursive sets. Third Convention Sci. Soc., Israel, 1959, pp. 1-2.
• 14: Rabin, M.O. Degree of difficulty of computing a function and a partial ordering of recursive sets. Tech. Rep. No. 1, O.N,R., Jerusalem, 1960.
• 15: Rabin, M.O. Probabilistic algorithms. In Algorithms and Complexity, New Directions and Recent Trends, J .F. Traub Ed., Academic Press, New York, 1976, pp. 21-39.
• 16: Sch6nhage, A., and Strassen, V. Schnelle Multiplication grosser Zahlen. Computing 7 (1971), 281-292.
• 17: Strassen, V. Gaussian elimination is not optimal. Num. Math. 13 (1969), 354-356.
• 18: Valiant, L.G. General context-free recognition in less than cubic time. Rep., Dept. Comptr. Sci., Carnegie-Mellon U., Pittsburgh, Pa., 1974.
• 19: S. Winograd, On the Time Required to Perform Addition, Journal of the ACM (JACM), v.12 n.2, p.277-285, April 1965 [doi>10.1145/321264.321279]
• 20: Winograd, S. On computing the discrete Fourier transform. Proc. Natl. Acad. Sci. USA 73 (1976), 1005-1006.

INDEX TERMS

Keywords:
algebraic complexity, complexity of computations, intractable problems, probabilistic algorithms