An overview of computational complexity

ABSTRACT

An historical overview of computational complexity is presented. Emphasis is on the fundamental issues of defining the intrinsic computational complexity of a problem and proving upper and lower bounds on the complexity of problems. Probabilistic and parallel computation are discussed.

REFERENCES

• 1: Adleman, L. Two theorems on random polynomial time. Proc. 19th IEEE Syrup. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1978), 75-83.
• 2: Adleman, L., Pomerance, C., and Rumiey, R. S. On distinguishing prime numbers from composite numbers, Annals of Math 117, (January 1983), 173-206.
• 3: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 4: Bennett, J. H. On Spectra. Doctoral dissertation, Department of Mathematics, Princeton University, 1962.
• 5: Berlekamp, E. R. Factoring polynomials over large finite fields. Math. Comp. 24 (1970), 713-735.
• 6: 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]
• 7: Blum, M., and Micali, S. How to generate cryptographically strong sequences of pseudo random bits. Proc. 23rd IEEE Syrup. on Foundations of Computer Science. IEEE Computer Society, Los Angeles. (1982), 112-117.
• 8: Borodin, A. On relating time and space to size and depth. SIAM J. Comp. 6 (1977), 733-744.
• 9: Borodin, A. Structured vs. general models in computational complexity. In Logic and Algorithmic Monographie no. 30 de L'Euseignement Mathematique Universite de Genuve, 1982.
• 10: Borodin, A. and Cook S. A time-space tradeoff for sorting on a general sequential model of computation. SLAM J. Comput. 11 (1982), 287-297.
• 11: Borodin, A., van zur Gathen, I. and Hopcroft, J. Fast parallel matrix and GCD computations. 23rd IEEE Syrup. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1982), 65-71.
• 12: Borodin, A. and Munro, I. The Computational Complexity of Algebraic and Numeric Problems. Elsevier, New York, 1975.
• 13: Brockett, R. W. and Dobkin, D. On the optimal evaluation of a set of bilinear forms. Linear Algebra and its Applications 19 (1978), 207-235.
• 14a: Gregory J. Chaitin, On the Length of Programs for Computing Finite Binary Sequences, Journal of the ACM (JACM), v.13 n.4, p.547-569, Oct. 1966 [doi>10.1145/321356.321363]
• 14b: Gregory J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM (JACM), v.22 n.3, p.329-340, July 1975 [doi>10.1145/321892.321894]
• 15: Cobham, A. The intrinsic computational difficulty of functious. Proc. 1964 International Congress for Logic, Methodology, and Philosophy of Sciences. Y. Bar-Hellel, Ed,, North Holland, Amsterdam, 1965, 24-30.
• 16: Cobham, A. The recognition problem for the set of perfect squares. IEEE Conference Record Seventh SWAT. (1966), 78-87.
• 17: Cohen, H. and Lenstra, H. W. Jr. Primarily testing and Jacobi sums. Report 82-18, University of Amsterdam, Dept. of Math., 1982.
• 18: 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]
• 19: Cook, S. A. Linear time simulation of deterministic two-way pushdown automata. Proc. IFIP Congress 71, (Theoretical Foundations). North Holland, Amsterdam, 1972, 7540.
• 20: Stephen A. Cook, An observation on time-storage trade off, Proceedings of the fifth annual ACM symposium on Theory of computing, p.29-33, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804032]
• 21: Cook, S. A. Towards a complexity, theory of synchronous parallel computation, L'Enseignement Mathdmatique XXVII (1981), 99-124.
• 22: Cook, S. A. and Aanderaa, S. O. On the minimum computation time of functions. Trans. AMS 142 (1969), 291-314.
• 23: Cooley, J. M. and Tukey, J. W. An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19 (1965), 297-301.
• 24: Coppersmith, D. and Winograd, S. On the asymptomatic complexity of matrix multiplication. SIAM J. Comp. 11 (1982), 472-492.
• 25: Diffie, W. and Hellman, M. E. New directions in cryptography. IEEE Trans. on Inform. Theory IT-22 6 (1976), 644-54.
• 26: Dobkin, D., Lipton, R. I. and Reiss, S. Linear programming is log-space hard for P. Inf. Processing Letters B (1979), 96-97.
• 27: Edmonds, J. Paths, trees, flowers. Conad. 1. Moth. 17 (1965), 449-67.
• 28: Edmonds, J. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B, 69 (1965), 67-72.
• 29: Ferrante, J. and Rackoff, C. W. The Computational Complexity of Logical Theories. Lecture Notes in Mathematics. #718, Springer Verlag, New York, 1979.
• 30: Fischer, M. J. and Rabin, M. O. Super-exponential complexity of Presburger arithmetic, In Complexity of Computation. SLAM-AMS Proc. 7, R. Karp, Ed., 1974, 27-42.
• 31: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 32: Gill, J. Computational complexity of probabilistic Turing machines. SLAM J. Comput. 6 (1977), 675-4595.
• 33: Leslie M. Goldschlager, A universal interconnection pattern for parallel computers, Journal of the ACM (JACM), v.29 n.4, p.1073-1086, Oct. 1982 [doi>10.1145/322344.322353]
• 34: Goldschlager, L. M., Shaw, R. A. and Staples, J. The maximum flow problem is log space complete for P. Theoretical Computer Science 21 (1982), 105-111.
• 35: Grzegorczyk, A. Some classes of recursive functions. Rozprawy Matematyczne, 1953.
• 36: Hartmanis, J. Observations about the development of theoretical computer science. Annals Hist. Comput. 3, 1 (Jan. 1981), 42-51.
• 37: Hartmanis, J. and Stearns, R. E. On the computational complexity of algorithms. Trans. AMS 117 (1965), 285-306.
• 38: Jones, N. D. and Laaser, W. T. Complete problems for deterministic polynomial time. Theoretical Computer Science 3 (1977), 105-117.
• 39: Erich Kaltofen, A polynomial reduction from multivariate to bivariate integral polynomial factorization., Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.261-266, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802200]
• 40: Kaltofen, E. A polynomial-time reduction from bivariate to univariate integral polynomial factorization. Preo. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles 1982, 57-64.
• 41: Karatsuba, A. and Ofman, Yu. Multiplication of multidigit numbers on automata. Doklady Akad. Nauk 145, 2 (1962), 293-294. Translated in Soviet Phys. Doklady. 7 7 (1963), 595-596.
• 42: Karp, R. M. Reducibility among combinatorial problems. In: Complexity of Computer Computations. R. E. Miller and J. W. Thatcher, Eds., Plenum Press, New York, 1972, 85-104.
• 43: Khachian, L. G. A polynomial time algorithm for linear programming. Doklady Akad. Nauk SSSR. 244, 5 (1979), 1093-96. Translated in Soviet Math. Doklady. 20, 191-194.
• 44: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 45: Kolmogorov, A. N. Three approaches to the concept of the amount of information. Probl. Pered. Inf. (Probl. of Inf Transm.) 1 (1965).
• 46: Kolmogorov, A. N. and Uspenski, V. A. On the definition of an algorithm, Uspehi Mat. Nauk. 13 (1958), 3-28; AMS Transl. 2nd sor. 29 (1963), 217- 245.
• 47: Richard E. Ladner, The circuit value problem is log space complete for P, ACM SIGACT News, v.7 n.1, p.18-20, January 1975 [doi>10.1145/990518.990519]
• 48: Lenstra, A. K., Lenstra, H. W. and Lovasz, L. Factoring polynomials with rational coefficients. Report 82-05, University of Amsterdam, Dept. of Math., 1982.
• 49: Levin, L. A. Universal search problems. Problemy Peredaei Informacii 9 (1973), 115-116. Translated in Problems of Information Transmission 9, 265- 266.
• 50: Luks, E. M. Isomorphism of graphs of bounded valence can be tested in polynomial time. Prec. 21st IEEE Syrup. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1980), 42-49.
• 51: Meyer, A. R. Weak monadic second-order theory of successor is not elementary-recursive. Lecture Notes in Mathematics. #453, Springer Verlag, New York, 1975, 132-154.
• 52: Meyer, A. R. and Steokmeyer, L. J. The equivalence problem for regular expressions with squaring requires exponential space. Proc. 13th IEEE Symp. on Switching and Automata Theory. (1972), 125-129.
• 53: Miller, G. L. Riemann's Hypothesis and tests for primality. J. Comput. System Sci. 13 (1976), 300-317.
• 54: Oppen, D. C. A 222p" upper bound on the complexity of Presburger arithmetic. J. Comput. Syst. Sci. 16 (1978), 323-332.
• 55: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 56: Paterson, M. S., Fischer, M. J. and Meyer, A. R. An improved overlap argument for on-line multiplication. SLAM-AMS Proc. 7, Amer. Math. Soc., Providence, 1974. 97-111.
• 57a: P(ppenger, N. On simultaneous resource bounds (preliminary version). Proc. 20th IEEE Syrup. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1979), 307-311.
• 57b: Nicholas Pippenger , Michael J. Fischer, Relations Among Complexity Measures, Journal of the ACM (JACM), v.26 n.2, p.361-381, April 1979 [doi>10.1145/322123.322138]
• 58: Vaughan R. Pratt , Michael O. Rabin , Larry J. Stockmeyer, A characterization of the power of vector machines, Proceedings of the sixth annual ACM symposium on Theory of computing, p.122-134, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803892]
• 59: Rabin, M. O. Speed of computation and classification of recursive sets. Third Convention SCi. Sac., Israel, 1959, 1-2.
• 60: Rabin, M. O. Degree of difificulty of computing a function and a partial ordering of recursive sets. Tech. Rep. No. 1, O.N.R., Jerusalem, 1960.
• 61: Rabin, M. O. Probabilistic algorithms. In Algorithms and Complexity, New Directions and Recent Trends, J. F. Traub, Ed., Academic Press, New York, 1976, 21-39.
• 62: Michael O. Rabin, Complexity of computations, Communications of the ACM, v.20 n.9, p.625-633, Sept. 1977 [doi>10.1145/359810.359816]
• 63: John H. Reif, Symmetric complementation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.201-214, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802193]
• 64: Reisch, S. and Schnitger, G. Three applications of Kolmorgorov complexity. Proc. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles. 1982, 45-52.
• 65: Robert Wells Ritchie, Classes of recursive functions of predictable complexity, 1961
• 66: Ritchie, R. W. Classes of predictably computable functions. Trans. AMS 106 (1963), 139-173.
• 67a: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 67b: Ruzzo, W.-L. On uniform circuit complexity. J. Comput. System SCi. 22 (1981), 365-383.
• 68a: John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
• 68b: Schnorr, C. P. The network complexity and the Turing machine complexity of finite functions. Acta Informatica 7 (1976), 95-107.
• 69: Sch6nhage, A. Storage modification machines. SIAM I. Comp. 9 (1980), 490- 508.
• 70: Schenhage, A. and Strassen, V. Schnelle Multiplication grosser Zahlen. Computing 7 (1971), 281-292.
• 71: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 72: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 73: Adi Shamir, On the Generation of Cryptographically Strong Pseudo-Random Sequences, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.544-550, July 13-17, 1981
• 74: Shannon, C. E. The synthesis of two terminal switching circuits. BSTJ 28 (1949), 59-98.
• 75: Smale, S. On the average speed of the simplex method of linear programruing. Preprint, 1982.
• 76: Smale, S. The problem of the average speed of the simplex method. Preprint, 1982.
• 77: Solovay, R. and Strassen, V. A fast monte-carlo test for primality. SLAM J. Comput. 6 (1977), 84--85.
• 78: Stearns, R. E., Hartmanis, J. and Lewis P. M. II. Hierarchies of memory limited computations. 6th IEEE Syrup. on Switching Circuit Theory and LogicalDesign. (1965), 179-190.
• 79: Stockmeyer, L. J. The complexity of decision problems in automata theory and logic. Doctoral Thesis, Dept. of Electrical Eng., M1T, Cambridge, MA., 1974; Report TR-133, MIT Laboratory for Computer Science.
• 80: Stockmeyer, L. J. Classifying the computational complexity of problems. Research Report RC 7606 (1979), Math. Sciences Dept., IBM T. J. Watson Research Center, Yorktown Heights, N.Y.
• 81: Strassen, V. Ganssian elimination is not optimal Num. Math. 13 (1969), 354- 356.
• 82: Strassen, V. Die Berechnungskomplexitfit von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numer. Math. 20 (1973), 238-251.
• 83: Baur, W. and Strassen, V. The complexity of partial derivatives. Preprint, 1982.
• 84: Toom, A. L. The complexity of a scheme of functional elements realizing the multiplication of integers. Doldady Akad. Nauk. SSSR 150 3, (1963) 496- 498. Translated in Soviet Math. Daklady 3 (1963), 714-716.
• 85: Turing, A. M. On computable numbers with an application to the Entscheidnungsproblem. Proc. London Math. SOc. ser. 2, 42 (1936-7), 230-265. A correction, ibid. 43 (1937), 544-546.
• 86: Valiant, L. G. The complexity of enumeration and reliability problems. SLAM J. Compat. 8 (1979), 410-421.
• 87: Valiant, L. G. The complexity of computing the permanent. Theoretical Computer Science 8 (1979), 189-202.
• 88: Valiant, L G. Parallel Computation. Proc. 7th IBM Japan Symp. Academic 6 Scientific Programs, IBM Japan, Tokyo (1982).
• 89: Leslie G. Valiant , Sven Skyum, Fast Parallel Computation of Polynomials Using Few Processes, Proceedings on Mathematical Foundations of Computer Science, p.132-139, August 31-September 04, 1981
• 90: van Neumarm, J. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games 1I. H. W. Kahn and A. W. Tucker, Eds. Princeton Univ. Press, Princeton, NJ, 1953.
• 91: Yamada, H. Real time computation and recursive functions not real-time computable.LBE Transactions on Electronic Computers. EC-11 (1962), 753- 760.
• 92: Yao, A. C. Theory and applications of trapdoor functions (Extended abstract). Proc. 23rd IEEE Syrup. on Foundations of Computer Science. lEVEE Computer Society, Los Angeles (1982), 80-91.

INDEX TERMS

Primary Classification:
  F. Theory of Computation

General Terms:
Theory

Keywords:
computational complexity