More Web Proxy on the site http://driver.im/

chapter

Free access

An overview of computational complexity

Author:

Stephen A. CookAuthors Info & Claims

ACM Turing award lectures

January 2007

Year awarded: 1982, Page 1982

https://doi.org/10.1145/1283920.1283938

Published: 01 January 2007 Publication History

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 Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1978), 75--83.

Digital Library

[2]

Adleman, L., Pomerance, C., and Rumley, R. S. On distinguishing prime numbers from composite numbers. Annals of Math 117 {January 1983), 173--206.

[3]

Aho, A. V., Hopcroft, J. E., and Ullman, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.

Digital Library

[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]

Blum, M. A machine independent theory of the complexity of recursire functions. JACM 14, 2 (April 1967), 322--336.

Digital Library

[7]

Blum, M., and Micali, S. How to generate cryptographically strong sequences of pseudo random bits. Proc. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1982), 112--117.

Digital Library

[8]

Borodin, A. On relating time and space to size and depth. SIAMJ. Comp. 6 (1977), 733--744.

[9]

Borodin, A. Structured vs. general models in computational complexity. In Logic and Algorithmic, Monographie no. 30 de L'Enseignement Mathematique Universitéde Genève, 1982.

[10]

Borodin, A., and Cook, S. A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput. 11 (1982), 287--297.

[11]

Borodin, A., von zur Gathen, J., and Hopcroft, J. Fast parallel matrix and GCD computations. 23rd IEEE Symp. 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.

[14]

Chaitin, G. J. On the length of programs for computing finite binary sequences. JACM 13, 4 {October 1966), 547--569; JACM 16, 1 (January 1969), 145--159,

Digital Library

[15]

Chaitin, G. J. A theory of program size formally identical to informational theory. JACM 22, 3 (July 1975), 329--340.

Digital Library

[16]

Cobham, A. The intrinsic computational difficulty of functions. Proc. 1964 International Congress for Logic, Methodology, and Philosophy of Sciences. Y. Bar-Hellel, Ed., North Holland, Amsterdam, 1965, 24--30.

[17]

Cobham, A. The recognition problem for the set of perfect squares. IEEE Conference Record Seventh SWAT (1966), 78--87.

Digital Library

[18]

Cohen, H., and Lenstra, H. W., Jr. Primarily testing and Jacobi sums. Report 82--18, University of Amsterdam, Dept. of Math., 1982.

[19]

Cook, S. A. The complexity of theorem proving procedures. Proc. 3rd ACM Symp. on Theory of Computing. Shaker Heights, Ohio (May 3--5, 1971), 151--158.

Digital Library

[20]

Cook, S. A. Linear time simulation of deterministic two-way pushdown automata. Proc. IFIP Congress 71 (Theoretical Foundations). North Holland, Amsterdam, 1972, 75--80.

[21]

Cook, S. A. An observation on time-storage tradeoff. JCSS 9 (1974), 308--316. Originally in Proc. 5th ACM Symp. on Theory of Computing, Austin, TX (April 30-May 2 1973), 29--33.

Digital Library

[22]

Cook, S. A. Towards a complexity theory of synchronous parallel computation. L'Enseignement Mathematique XXVII (1981), 99--124.

[23]

Cook, S. A., and Aanderaa, S. O. On the minimum computation time of functions. Trans. AMS 142 (1969), 291--314.

[24]

Cooley, J. M., and Tukey, J. W. An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19 (1965), 297--301.

[25]

Coppersmith, D., and Winograd, S. On the asymptomatic complexity of matrix multiplication. SIAM J. Comp. 11 (1982), 472--492.

[26]

Diffie, W., and Hellman, M. E. New direction in cryptography. IEEE Trans. on Inform. Theory IT-22, 6 (1976), 644--654.

Digital Library

[27]

Dobkin, D., Lipton, R. J., and Reiss, S. Linear programming is log-space hard for P. Inf. Processing Letters 8 (1979), 96--97.

[28]

Edmonds, J. Paths, trees, flowers. Canad. J. Math. 17 (1965), 449--67.

[29]

Edmonds, J. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B, 69 (1965), 67--72.

[30]

Ferrante, J., and Rackoff, C. W. The Computational Complexity of Logical Theories. Lecture Notes in Mathematics. #718, Springer Verlag, New York, 1979.

[31]

Fischer, M. J., and Rabin, M. O. Super-exponential complexity of Presburger arithmetic. In Complexity of Computation. SIAM-AMS Proc. 7, R. Karp, Ed., 1974, 27--42.

[32]

Garey, M. R., and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.

Digital Library

[33]

Gill, J. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977), 675--695.

Digital Library

[34]

Goldschlager, L. M. Synchronous Parallel Computation. Doctoral dissertation, Dept. of Computer Science, Univ. of Toronto, 1977. See also JACM 29, 4 (October 1982), 1073--1086.

[35]

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.

[36]

Grzegorczyk, A. Some classes of recursive functions. Rozprawy Matemtyczne, 1953.

[37]

Hartmanis, J. Observations about the development of theoretical computer science. Annals Hist. Comput. 3, 1 (Jan. 1981), 42--51.

Digital Library

[38]

Hartmanis, J., and Stearns, R. E. On the computational complexity of algorithms. Trans. AMS 117 (1965), 285--306.

[39]

Jones, N. D., and Laaser, W. T. Complete problems for deterministic polynomial time. Theoretical Computer Science 3 (1977), 105--427.

[40]

Kaltofen, E. A polynomial reduction from multivariate to bivariate integer polynomial factorization. Proc. 14th ACM Symp. in Theory Comp., San Francisco, CA (May 5--7 1982), 261--266.

Digital Library

[41]

Kaltofen, E. A polynomial-time reduction from bivariate to univariate integral polynomial factorization. Proc. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1982), 57--64.

Digital Library

[42]

Karatsuba, A., and Ofman, Yu. Multiplication of multidigit numbers on automata. Doklady Akad. Nauk 145, 2 (1962), 293--294. Translated in Soviet Phys. Doklady 77 (1963), 595--596.

[43]

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.

[44]

Khachian, L. G. A polynomial time algorithm for linear programming. Doklady Akad. Nauh SSSR. 244, 5(1979), 1093--96. Translated in Soviet Math. Doklady 20, 191--194.

[45]

Knuth, D. E. The Art of Computer Programming, vol. 3. Sorting and Searching. Addison-Wesley, Reading, MA, 1973.

[46]

Kolmogorov, A. N. Three approaches to the concept of the amount of information. Probl. Pered. Inf. (Probl. of Inf Transm.) 1 (1965).

[47]

Kolmogorov, A. N., and Uspenski, V. A. On the definition of an algorithm, Uspehi Mat. Nauk. 13 (1958), 3--28: AMS Transl. 2nd ser. 29 (1963), 217--245.

[48]

Ladner, R. E. The circuit value problem is log space complete for P. SIGACT News 7, 1 (1975), 18--20.

Digital Library

[49]

Lenstra, A. K., Lenstra, H. W., and Lovasz, L. Factoring polynomials with rational coefficients. Report 82-05, University of Amsterdam, Dept. of Math., 1982.

[50]

Levin, L. A. Universal search problems. Problemy Peredaci lnformacii 9 (1973), 115--116. Translated in Problems of Information Transmission 9, 265--266.

[51]

Luks, E. M. Isomorphism of graphs of bounded valence can be tested in polynomial time. Proc. 21st IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1980), 42--49.

Digital Library

[52]

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.

[53]

Meyer, A. R., and Stockmeyer, 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.

Digital Library

[54]

Miller, G. L. Riemann's hypothesis and tests for primality. J. Comput. System Sci. 13 (1976), 300--317.

Digital Library

[55]

Oppen, D. C. A 222p upper bound on the complexity of Presburger arithmetic. J. Comput. Syst. Sci. 16 (1978), 323--332.

[56]

Papadimitriou, C. H., and Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982.

Digital Library

[57]

Paterson, M. S., Fischer, M. J., and Meyer, A. R. An improved overlap argument for on-line multiplication. SIAM-AMS Proc. 7, Amer. Math. Soc., Providence, 1974, 97--111.

[58]

Pippenger, N. On simultaneous resource bounds (preliminary version). Proc. 20th IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles {1979), 307--311.

[59]

Pippenger, N. J., and Fischer, M. J. Relations among complexity measures. JACM 26, 2 (April 1979), 361--381.

Digital Library

[60]

Pratt, V. R., and Stockmeyer, L. J. A characterization of the power of vector machines. J. Comput. System Sci. 12 (1976), 198--221. Originally in Proc. 6th ACM Symp. on Theory of Computing, Seattle, WA (April 30-May 2, 1974), 122--134.

Digital Library

[61]

Rabin, M. O. Speed of computation and classification of recursive sets. Third Convention Sci. Soc., Israel, 1959, 1--2.

[62]

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, 1950.

[63]

Rabin, M. O. Probabilistic algorithms. In Algorithms and Complexity, New Directions and Recent Trends, J. F. Traub, Ed., Academic Press, New York, 1976, 29--39.

[64]

Rabin, M. O. Complexity of computations. Comm. ACM 20, 9 (September 1977), 625--633.

Digital Library

[65]

Reif, J. H. Symmetric complementation. Proc. 14th ACM Symp. on Theory of Computing, San Francisco, CA (May 5--7, 1982), 201--214.

Digital Library

[66]

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.

[67]

Ritchie, R. W. Classes of Recursive Functions of Predictable Complexity. Doctoral Dissertation, Princeton University, 1960.

Digital Library

[68]

Ritchie, R. W. Classes of predictably computable functions. Trans. AMS 106 (1963), 139--173.

[69]

Rivest, R. L., Shamir, A., and Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM 21, 2 (February 1978), 120--126.

Digital Library

[70]

Ruzzo, W. L. On uniform circuit complexity. J. Comput. System Sci. 22 (1981), 365--383.

[71]

Savage, J. E. The Complexity of Computing. Wiley, New York, 1976.

Digital Library

[72]

Schnorr, C. P. The network complexity and the Turing machine complexity of finite functions. Acta Informatica 7 (1976), 95--107.

Digital Library

[73]

SchSnhage, A. Storage modification machines. SIAM J. Comp. 9 (1980), 490--508.

[74]

Schönhage, A., and Strassen. V. Schnelle Multiplication grosser Zahlen. Computing 7 (1971), 281--292.

[75]

Schwartz, J. T. Probabilistic algorithms for verification of polynomial identities. JACM 27, 4 (October 1980), 701--717.

Digital Library

[76]

Schwartz, J. T. Ultracomputers. ACM Trans. on Prog. Languages and Systems 2, 4 (October 1980), 484--521.

Digital Library

[77]

Shamir, A. On the generation of cryptographically strong pseudo random sequences. 8th Int. Colloquium on Automata, Languages, and Programming (July 1981). Lecture Notes in Computer Science 115. Springer Verlag, New York, 544--550.

Digital Library

[78]

Shannon, C. E. The synthesis of two terminal switching circuits. BST28 (1949), 59--98.

[79]

Smale, S. On the average speed of the simplex method of linear programming. Preprint, 1982.

[80]

Smale, S. The problem of the average speed of the simplex method. Preprint, 1982.

[81]

Solovay, R., and Strassen, V. A fast monte-carlo test for primality. SlAM J. Comput. 6 (1977), 84--85.

[82]

Stearns, R. E., Hartmanis, J., and Lewis, P. M. II Hierarchies of memory limited computations. 6th IEEE Symp. on Switching Circuit Theory and Local Design (1965), 179--190.

[83]

Stockmeyer, L. J. The complexity of decision problems in automata theory and logic. Doctoral Thesis, Dept. of Electrical Eng., MIT, Cambridge, MA., 1974; Report TR-133, MIT, Laboratory for Computing Science.

[84]

Stockmeyer, L. J. Classifying the computational complexity of problems. Research Report RC 7606 (1979), Math. Sciences Dept., IBM TJ. Watson Research Center, Yorktown Heights, N.Y.

[85]

Strassen, V. Gaussian elimination is not optimal. Num. Math. 13 (1969), 354--356.

Digital Library

[86]

Strassen, V. Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numer. Math. 20 (1973), 238--251.

Digital Library

[87]

Baur, W., and Strassen, V. The complexity of partial derivatives. Preprint, 1982.

[88]

Toom, A. L. The complexity of a scheme of functional elements realizing the multiplication of integers. Doklady Akad. Nauk. SSSR 150, 3 (1963), 496--498. Translated in Souiet Math. Doklady 3 (1963), 714--716.

[89]

Turing, A. M. On computable numbers with an application to the Entscheidnungsproblem. Proc. London Math. Soc. ser. 2, 42 (1963--7), 230--265. A correction, ibid. 43 (1937), 544--546.

[90]

Valiant, L. G. The complexity of enumeration and reliability problems. SIAM J. Comput. 8 (1979), 189--202.

[91]

Valiant, L. G. The complexity of computing the permanent. Theoretical Computer Science 8 (1979), 189--202.

[92]

Valiant, L. G. Parallel computation. Proc. 7th IBM J. apan Symp. Academic 6 Scientific Programs, IBM Japan, Tokyo (1982).

[93]

Valiant, L. G., Skyum, S., Berkowitz, S., and Rackoff, C. Fast parallel computation on polynomials using few processors. Preprint (Preliminary version in Springer Lecture Notes in Computer Science 118 (1981), 132--139.

Digital Library

[94]

von Neumann, J. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games II. H. W. Kahn and A. W. Tucker, Eds. Princeton Univ. Press, Princeton, N.J. 1953.

[95]

Yamada, H. Real time computation and recursive functions not real-time computable. IRE Transactions on Electronic Computers EC-11 (1962), 753--760.

[96]

Yao, A. C. Theory and applications of trapdoor functions (extended abstract). Proc. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1982), 80--91.

Cited By

Olliaro MPérez Gort MCortesi A(2022)Empirical analysis of the impact of queries on watermarked relational databasesExpert Systems with Applications10.1016/j.eswa.2022.117491204(117491)Online publication date: Oct-2022
https://doi.org/10.1016/j.eswa.2022.117491
Saophan PPannakkong W(2022)A Genetic Algorithm Based Artificial Neural Network for Production Rescheduling ProblemIntegrated Uncertainty in Knowledge Modelling and Decision Making10.1007/978-3-030-98018-4_23(279-290)Online publication date: 4-Mar-2022
https://doi.org/10.1007/978-3-030-98018-4_23

Index Terms

An overview of computational complexity
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials
  2. Probability and statistics
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models
    2. Probabilistic computation

Recommendations

An overview of computational complexity

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 ...
Evaluation and analysis of computational complexity for secure multicast models
ICCSA'03: Proceedings of the 2003 international conference on Computational science and its applications: PartII

Multicast is an internetwork service that provides efficient delivery of packets from a single source to multiple recipients. When there are large number of members in the group, security and scalability problems arise and an attempt to solve this, ...
Computational Complexity of Two-Dimensional Regions

The computational complexity of bounded sets of the two-dimensional plane is studied in the discrete computational model. We introduce four notions of polynomial-time computable sets in R$^2$ and study their relationship. The computational complexity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other Books

ACM Turing award lectures

January 2007

396 pages

ISBN:9781450310499

DOI:10.1145/1283920

Copyright © 2007.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2007

Permissions

Request permissions for this article.

Request Permissions

Author Tags

Qualifiers

Chapter

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
3,289
Total Downloads

Downloads (Last 12 months)564
Downloads (Last 6 weeks)75

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Olliaro MPérez Gort MCortesi A(2022)Empirical analysis of the impact of queries on watermarked relational databasesExpert Systems with Applications10.1016/j.eswa.2022.117491204(117491)Online publication date: Oct-2022
https://doi.org/10.1016/j.eswa.2022.117491
Saophan PPannakkong W(2022)A Genetic Algorithm Based Artificial Neural Network for Production Rescheduling ProblemIntegrated Uncertainty in Knowledge Modelling and Decision Making10.1007/978-3-030-98018-4_23(279-290)Online publication date: 4-Mar-2022
https://doi.org/10.1007/978-3-030-98018-4_23

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Chapter

Media

Figures

Other

Tables

View Table of Contents