A short introduction to implicit computational complexity. (English) Zbl 1250.03066
Bezhanishvili, Nick (ed.) et al., Lectures on logic and computation. ESSLLI 2010 Copenhagen, Denmark, August 2010, ESSLLI 2011, Ljubljana, Slovenia, August 2011. Selected lecture notes. Berlin: Springer (ISBN 978-3-642-31484-1/pbk). Lecture Notes in Computer Science 7388, 89-109 (2012).
Summary: These lecture notes are meant to serve as a short introduction to implicit computational complexity for those students who have little or no knowledge of recursion theory and proof theory. They have been obtained by enriching and polishing a set of notes the author wrote for a course (on the same subject) he gave at ESSLLI 2010. These notes are definitely not meant to be comprehensive nor exhaustive, but on the other hand much effort has been done to keep them self-contained.
For the entire collection see [Zbl 1248.03007].
For the entire collection see [Zbl 1248.03007].
MSC:
| 03D15 | Complexity of computation (including implicit computational complexity) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, New York (2009) · Zbl 1193.68112 · doi:10.1017/CBO9780511804090 |
| [2] | Baader, F., Nipkow, T.: Term rewriting and all that. Cambridge University Press (1998) · Zbl 0948.68098 · doi:10.1017/CBO9781139172752 |
| [3] | Barendregt, H.P.: The Lambda Calculus – Its Syntax and Semantics. North-Holland (1984) · Zbl 0551.03007 |
| [4] | Bellantoni, S., Cook, S.A.: A new recursion-theoretic characterization of the polytime functions. Computational Complexity 2, 97–110 (1992) · Zbl 0766.68037 · doi:10.1007/BF01201998 |
| [5] | Bonfante, G., Cichon, A., Marion, J.-Y., Touzet, H.: Algorithms with polynomial interpretation termination proof. Journal of Functional Programming 11(1), 33–53 (2001) · Zbl 0987.68042 · doi:10.1017/S0956796800003877 |
| [6] | Bonfante, G., Marion, J.-Y., Moyen, J.-Y.: Quasi-interpretations a way to control resources. Theoretical Computer Science 412(25), 2776–2796 (2011) · Zbl 1230.68077 · doi:10.1016/j.tcs.2011.02.007 |
| [7] | Cobham, A.: The intrinsic computational difficulty of functions. In: Bar-Hillel, Y. (ed.) Logic, Methodology and Philosophy of Science, Proceedings of the 1964 International Congress, pp. 24–30. North-Holland (1965) · Zbl 0192.08702 |
| [8] | Cutland, N.: Computability: An Introduction to Recursive Function Theory. Cambridge University Press (1980) · Zbl 0448.03029 |
| [9] | Girard, J.-Y.: Light linear logic. Information and Computation 143(2), 175–204 (1998) · Zbl 0912.03025 · doi:10.1006/inco.1998.2700 |
| [10] | Hartmanis, J., Stearns, R.: On the computational complexity of algorithms. Transactions of the American Mathematical Society 117, 285–306 (1965) · Zbl 0131.15404 · doi:10.1090/S0002-9947-1965-0170805-7 |
| [11] | Hindley, J.R., Seldin, J.P.: Lambda-Calculus and Combinators: An Introduction. Cambridge University Press (2008) · Zbl 1149.03016 · doi:10.1017/CBO9780511809835 |
| [12] | Hofmann, M.: Linear types and non-size-increasing polynomial time computation. Information and Computation 183(1), 57–85 (2003) · Zbl 1054.68065 · doi:10.1016/S0890-5401(03)00009-9 |
| [13] | Kristiansen, L., Niggl, K.-H.: On the computational complexity of imperative programming languages. Theoretical Computer Science 318(1-2), 139–161 (2004) · Zbl 1048.03030 · doi:10.1016/j.tcs.2003.10.016 |
| [14] | Lafont, Y.: Soft linear logic and polynomial time. Theoretical Computer Science 318(1-2), 163–180 (2004) · Zbl 1079.03057 · doi:10.1016/j.tcs.2003.10.018 |
| [15] | Leivant, D.: Stratified functional programs and computational complexity. In: Proceedings of Twentieth Annual Symposium on Principles of Programming Languages, pp. 325–333 (1993) · doi:10.1145/158511.158659 |
| [16] | Leivant, D., Marion, J.-Y.: Lambda Calculus Characterizations of Poly-Time. In: Bezem, M., Groote, J.F. (eds.) TLCA 1993. LNCS, vol. 664, pp. 274–288. Springer, Heidelberg (1993) · Zbl 0788.68051 · doi:10.1007/BFb0037112 |
| [17] | Leivant, D., Marion, J.-Y.: Ramified Recurrence and Computational Complexity II: Substitution and Poly-Space. In: Bezem, M., Groote, J.F. (eds.) TLCA 1993. LNCS, vol. 664, pp. 486–500. Springer, Heidelberg (1993) · Zbl 1044.03526 · doi:10.1007/BFb0037112 |
| [18] | Marion, J.-Y.: Analysing the implicit complexity of programs. Information and Computation 183(1), 2–18 (2003) · Zbl 1054.68073 · doi:10.1016/S0890-5401(03)00011-7 |
| [19] | Neergaard, P.M.: A Functional Language for Logarithmic Space. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, pp. 311–326. Springer, Heidelberg (2004) · Zbl 1116.68377 · doi:10.1007/978-3-540-30477-7_21 |
| [20] | Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1993) · Zbl 0557.68033 |
| [21] | Rogers, H.: The Theory of Recursive Functions and Effective Computability. MIT Press (1987) |
| [22] | Terui, K.: Light affine lambda calculus and polynomial time strong normalization. Archive for Mathematical Logic 46(3-4), 253–280 (2007) · Zbl 1110.03009 · doi:10.1007/s00153-007-0042-6 |
| [23] | Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 2, 230–265 (1937) · Zbl 0016.09701 · doi:10.1112/plms/s2-42.1.230 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
