Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Turing and the development of computational complexity
Published online by Cambridge University Press: 05 June 2014
Edited by
Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Summary
Abstract. Turing's beautiful capture of the concept of computability by the “Turing machine” linked computability to a device with explicit steps of operations and use of resources. This invention led in a most natural way to build the foundations for computational complexity.
§1. Introduction. Computational complexity provides mechanisms for classifying combinatorial problems and measuring the computational resources necessary to solve them. The discipline provides explanations of why no practical solutions to certain problems have been found, and provides a way of anticipating difficulties involved in solving these problems. The classification is quantitative and is intended to investigate what resources are necessary, lower bounds, and what resources are sufficient, upper bounds, to solve various problems.
This classification should not depend on a particular computational model but rather should measure the intrinsic difficulty of a problem. Precisely for this reason, as we will explain, the basic model of computation for our study is the multitape Turing machine.
Computational complexity theory today addresses issues of contemporary concern, for example, parallel computation, circuit design, computations that depend on random number generators, and development of efficient algorithms. Above all, computational complexity is interested in distinguishing problems that are efficiently computable. Algorithms whose running times are n2 in the size of their inputs can be implemented to execute efficiently even for fairly large values of n, but algorithms that require an exponential running time can be executed only for small values of n.
- Type
- Chapter
- Information
- Turing's LegacyDevelopments from Turing's Ideas in Logic, pp. 299 - 328Publisher: Cambridge University PressPrint publication year: 2014
References
[AH87] and , Recognizing primes in random polynomial time, Proceedings of the nineteenth annual ACM Symposium on Theory of Computing, 1987, pp. 462-469.
[AM77] and , Reducibility, randomness, and intractability, Proceedings of the ninth annual ACM Symposium on Theory of Computing, 1977,pp. 151-163.
[AKS04] , , and , Primes is in P, Annals of Mathematics, vol. 160 (2004), no. 2, pp. 781-793.Google Scholar
[Ajt83] , formulea on finite structures, Journal of Pure and Applied Logic, vol. 24 (1983), pp. 1-48.Google Scholar
[AS89] , On the relative complexity of hard problems for complexity classes without complete problems, Theoretical Computer Science, vol. 63 (1989), pp. 43-61.Google Scholar
[Aro98] , Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM, vol. 45 (1998), no. 5, pp. 753-782.Google Scholar
[ALM+92] , , , , and , Proof verification and hardness of approximation problems, Proceedings of the thirty-third symposium on Foundations of Computer Science, IEEE Computer Society, 1992, pp. 14-23.
[AS98] and , Probabilistic checking of proofs: A new characterization of NP, Journal of the ACM, vol. 45 (1998), no. 1, pp. 70-122.Google Scholar
[Bab85] , Trading group theory for randomness, Proceedings of the 17th annual ACM Symposium on Theory of Computing, 1985, pp. 421-429.
[BFLS91] , , , and , Checking computations in polylogarithmic time, Proceedings of the 23rd ACM Symposium on the Theory of Computing, 1991, pp. 21-31.
[BFNW93] , , , and , BPP has subexponential simulations unless EXPTIME has publishable proofs, Computational Complexity, vol. 3 (1993), pp. 307-318.Google Scholar
[BM84] and , How to generate cryptographically strong sequences of pseudorandom bits, SIAM Journal on Computing, vol. 13 (1984), pp. 850-864.Google Scholar
[Boo72] , On languages accepted in polynomial time, SIAM Journal on Computing, vol. 1 (1972), no. 4, pp. 281-287.Google Scholar
[Boo76] , Translational lemmas, polynomial time, and (log n)j-space, Theoretical Computer Science, vol. 1 (1976), pp. 215-226.Google Scholar
[BG70] and , Quasi-realtime languages, Mathematical Systems Theory, vol. 4 (1970), pp. 97-111.Google Scholar
[BHZ87] , , and , Does co-NP have short interactive proofs?, Information Processing Letters, vol. 25 (1987), no. 2, pp. 127-132.Google Scholar
[Bor77] , On relating time and space to size and depth, SIAM Journal on Computing, vol. 6 (1977), pp. 733-744.Google Scholar
[CKS81] , , and , Alternation, Journal of the ACM, vol. 28 (1981), no. 1, pp. 114-133.Google Scholar
[Chu36] , An unsolvable problem of elementary number theory, American Journal of Mathematics, vol. 58 (1936), pp. 345-363.Google Scholar
[Cob64] , The intrinsic computational difficulty of functions, Proceedings of the 1964 international congress for Logic, Methodology, and the Philosophy of Science, North Holland, 1964, pp. 24-30.
[Coo71a] , Characterizations of pushdown machines in terms of time-bounded computers, Journal of the ACM, vol. 19 (1971), pp. 175-183.Google Scholar
[Coo71b] , The complexity of theorem-proving procedures, Proceedings of the third ACM Symposium on Theory of Computing, 1971, pp. 151-158.
[Coo73] , A hierarchy for nondeterministic time complexity, Journal of Computer and System Sciences, vol. 7 (1973), no. 4, pp. 343-353.Google Scholar
[Coo79] , Deterministic CFL's are accepted simultaneously in polynomial time and log squared space, Proceedings of the 11th annual ACM Symposium on Theory of of Computing, 1979, pp. 338-345.
[Dav06a] , The Church–Turing thesis: Consensus and opposition, CiE'06, 2006, pp. 125-132.
[Dav06b] , Why there is no such discipline as hypercomputation, Applied Mathematics and Computation, (2006), pp. 4-7.
[DL78] and , A probabilstic remark on algebraic program testing, Information Processing Letters, vol. 7 (1978), no. 4, pp. 193-195.Google Scholar
[Edm65] , Paths, trees, and flowers, Canadian Journal of Mathematics, vol. 17 (1965), pp. 449-467.Google Scholar
[ET76] and , A combinatorial problem which is complete in polynomial space, Journal of the ACM, vol. 23 (1976), pp. 710-719.Google Scholar
[FGL+96] , , , , and , Interactive proofs and the hardness of approximating cliques, Journal of the ACM, vol. 43 (1996), pp. 268-292.Google Scholar
[Fel86] , The optimumprover lives in PSPACE, manuscript, 1986.
[FH03] and , A brief history of complexity theory, Bulletin of the European Assocation for Theoretical Computer Science, vol. 80 (2003), pp. 95-133.Google Scholar
[FS11] and , Robust simulations and significant separations, Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 6755, Springer, 2011, pp. 569-580.
[FSS84] , , and , Parity, circuits, and the polynomial-time hierarchy, Mathematical Systems Theory, vol. 17 (1984), no. 1, pp. 13-28.Google Scholar
[GJ79] and , Computers and intractability: A guide to the theory of NP-completeness, , San Francisco, 1979.
[Gil77] , Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, vol. 6 (1977), no. 4, pp. 675-695.Google Scholar
[GKL88] , , and , On the existence of pseudorandom generators, Proceedings of the 29th annual IEEE symposium on Foundations of Computer Science, 1988, pp. 12-24.
[GL89] and , Hard-core predicates for any one-way function, Proceedings of the 21st annual ACM Symposium on Theory of Computation, 1989, pp. 25-32.
[GMW91] , , and , Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proofs, Journal of the ACM, vol. 38 (1991), no. 3, pp. 691-729.Google Scholar
[GMR89] , , and , The knowledge complexity of interactive proof systems, SIAM Journal on Computing, vol. 18 (1989), no. 1, pp. 186-208.Google Scholar
[GHR95] , , and , Limits to parallel computation: P-completeness theory, Oxford University Press, New York, NY, 1995.
[HH86] and , Complexity classes without machines: on complete languages for UP, Proceedings of the 13th International Colloquium on Automata, Languages, and Programming (Berlin), Lecture Notes in Computer Science, Springer-Verlag, 1986, pp. 123-135.
[HLS65] , , and , Hierarchies of memory limited computations, Proceedings of the sixth annual IEEE Symposium on Switching Circuit Theory and Logical Design, 1965, pp. 179-190.
[HS65] and , On the computational complexity of algorithms, Transactions of the American Mathematical Society, vol. 117 (1965), pp. 285-306.Google Scholar
[Has99] , Clique is hard to approximate within n1-∈, Acta Mathematica, vol. 182 (1999), pp. 105-142.Google Scholar
[Has01] , Some optimal inapproximabiity results, Journal of the ACM, vol. 48 (2001), pp. 798-849.Google Scholar
[HILL91] , , , and , Construction of a pseudorandom generator from any one-way function, Technical report, ICSI, Berkely, CA, 1991.
[HS11] and , Computability and complexity theory, 2nd ed., Texts in Computer Science, Springer-Verlag, New York, NY, December 2011.
[Iba72] , A note concerning nondeterministic tape complexities, Journal of Computer and System Sciences, vol. 19 (1972), no. 4, pp. 609-612.Google Scholar
[Imm88] , Nondeterministic space is closed under complementation, SIAM Journal on Computing, vol. 17 (1988), no. 5, pp. 935-938.Google Scholar
[IW97] and , P = BPP if E requires exponential circuits: Derandomizing the XOR lemma, Proceedings of the 29th ACM Symposium on the Theory of Computing, ACM, New York, 1997, pp. 220-229.
[Ins00] Clay Mathematics Institute, Millennium prize problems, http://www.claymath. org/prizeproblems/, 2000.
[Jon73] , Reducibility among combinatorial problems in log n space, Proceedings of the seventh annual Princeton Conference on Information Sciences and Systems (Princeton, NJ), Department of Electrical Engineering, Princeton University, 1973, pp. 547-551.
[Jon75] , Space-bounded reducibility among combinatorial problems, Journal of Computer and System Sciences, vol. 11 (1975), pp. 68-85.Google Scholar
[JS74] and , Turing machines and the spectra of first-order formulas, The Journal of Symbolic Logic, vol. 29 (1974), pp. 139-150.Google Scholar
[Kar72] , Reducibility among combinatorial problems, Complexity of computer computations, Plenum Press, New York, 1972, pp. 85-104.
[KL80] and , Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM Symposium on the Theory of Computing, 1980, an extended version has appeared in L'Enseignement Mathématique, 2nd series 28, 1982, pp. 191–209, pp. 302-309.
[Kur64] , Classes of languages and linear bounded automata, Information and Control, vol. 7 (1964), no. 2, pp. 207-223.Google Scholar
[LLS75] , , and , A comparison of polynomial time reducibilities, Theoretical Computer Science, vol. 1 (1975), pp. 103-123.Google Scholar
[Lau83] , BPP and the polynomial hierarchy, Information Processing Letters, vol. 17 (1983), pp. 215-217.Google Scholar
[Lev73] , Universal sorting problems, Problems of Information Transmission, vol. 9 (1973), pp. 265-266, English translation of original in Problemy Peredaci Informacii.Google Scholar
[LFKN90] , , , and , Algebraic methods for interactive proof systems, Proceedings of the 31st IEEE symposium on Foundations of Computer Science, 1990, pp. 2-10.
[Mag69] , Writing pushdown acceptors, Journal of Computer and System Sciences, vol. 3 (1969), no. 3, pp. 276-319.Google Scholar
[MS72] and , The equivalence problem for regular expressions with squaring requires exponential space, Proceedings of the thirteenth IEEE symposium on Switching and Automata Theory, 1972, pp. 125-129.
[Mil76] , Reimann's hypothesis and tests for primality, Journal of Computer and System Sciences, vol. 13 (1976), pp. 300-317.Google Scholar
[Myh60] , Linear bounded automata, WADD 60-165, Wright Patterson AFB, Ohio, 1960.
[NW94] and , Hardness vs. randomness, Journal of Computer and System Sciences, vol. 49 (1994), pp. 149-167.Google Scholar
[PY91] and , Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, vol. 43 (1991), pp. 425-440.Google Scholar
[PPST83] , , , and , On determinism and non-determinism and related problems, Proceedings of the twenty fourth ACM Symposium on Theory of Computing, 1983, pp. 429-438.
[Pip79] , On simultaneous resource bounds, Proceedings of the 20th annual IEEE symposium on Foundations of Computer Science, 1979, pp. 307-311.
[PF79] and , Relations among complexity measures, Journal of the ACM, vol. 26 (1979), pp. 361-381.Google Scholar
[Pra75] , Every prime has a succinct certificate, SIAM Journal on Computing, vol. 4 (1975), pp. 214-220.Google Scholar
[Rab80] , Probabilistic algorithms for testing primality, Journal of Number Theory, vol. 12 (1980), pp. 128-138.Google Scholar
[RS59] and , Finite automata and their decision problems, IBM Journal, (1959), pp. 114-125.Google Scholar
[Ros67] , Real-time definable languages, Journal of the ACM, vol. 14 (1967), pp. 645-662.Google Scholar
[Sav72] , Computational work and time on finite machines, Journal of the ACM, vol. 19 (1972), pp. 660-674.Google Scholar
[Sav70] , Relationships between nondeterministic and deterministic time complexities, Journal of Computer and System Sciences, vol. 4 (1970), no. 2, pp. 177-192.Google Scholar
[Sch80] , Fast probabilistic algorithms for verification of polynomial identities, Journal of the ACM, vol. 27 (1980), pp. 701-717.Google Scholar
[Sha90] , IP=PSPACE, Proceedings of the 31st IEEE symposium on Foundations of Computer Science, 1990, pp. 145-152.
[Sha49] , The synthesis of two–terminal switching circuits, Bell System Technical Journal, vol. 28 (1949), pp. 59-98.Google Scholar
[SG77] and , Polynomial reducibilities and upward diagonalizations, Proceedings of the ninth annual ACM Symposium on Theory of Computing, 1977, pp. 186-194.
[Sip78] , Halting space-bounded computations, Proceedings of the 19th annual IEEE symposium on Foundations of Computer Science, 1978, pp. 73-74.
[Sip82] , On relativization and the existence of complete sets, Automata, languages, and programming, Lecture Notes in Computer Science, vol. 140, Springer-Verlag, 1982.
[Sip83] , A complexity theoretic approach to randomness, Proceedings of the fifteenth ACM Symposium on Theory of Computing, 1983, pp. 330-335.
[SS77] and , A fast Monte-Carlo test for primality, SIAM Journal on Computing, vol. 6 (1977), pp. 84-85.Google Scholar
[Sto76] , The polynomial-time hierarchy, Theoretical Computer Science, vol. 3 (1976), pp. 1-22.Google Scholar
[Sze88] , The method of forced enumeration for nondeterministic automata, Acta Informatica, vol. 26 (1988), pp. 279-284.Google Scholar
[Tod89] , On the computational power of PP and ⊕P, Proceedings of the 30th IEEE symposium on Foundations of Computer Science, 1989, pp. 514-519.
[Tre04] , Inapprox imability of combinatorial optimization problems, The Electronic Colloquium in Computational Complexity, (2004), pp. 1-39, Technical Report 65.
[Tur36] , On computable numbers with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 42 (1936), pp. 230-365.Google Scholar
[Tur39] , Systems of logic based on ordinals, Proceedings of the London Mathematical Society, vol. 45 (1939), pp. 161-228.Google Scholar
[Wra76] , Complete sets and the polynomial hierarchy, Theoretical Computer Science, vol. 3 (1976), pp. 23-33.Google Scholar
[Yao82] , Theory and applications of trapdoor functions, Proceedings of the 23rd IEEE symposium on Foundations of Computer Science, 1982, pp. 80-91.
[Yao85] , Separating the polynomial-time hierarchy by oracles, Proceedings of the 26th IEEE symposium on Foundations of Computer Science, 1985, pp. 1-10.
[Zak83] , A Turingmachine timehierarchy, Theoretical Computer Science, vol. 26 (1983), pp. 327-333.Google Scholar
[Zip79] , Probabilistic algorithms for sparse polynomials, Lecture Notes in Computer Science, vol. 72, Springer, 1979.