96 words
The invariance thesis (see Arora and Barak (Complexity), § 1.3.1; Dean (‘Complexity’), § 2.2; van Emde Boas (‘Models’), § 1; Levesque (‘Complexity’), § 1) that ‘[t]here exists a standard class of machine models…[that] simulate each other with Polynomially bounded overhead in time and constant factor overhead in space’ appears to have been partially anticipated by Levesque (ibid.) (§ 3).
Turing complexity thesis. Anything that can be computed at all can be computed by a Turing machine with at most a polynomial slowdown.
… Corollary. Anything that a Turing machine cannot calculate in polynomial time cannot be calculated at all in polynomial time.
References
Arora, Sanjeev and Boaz Barak, Complexity: Computational Complexity: A Modern Approach, Cambridge University Press, 2009. |
Dean, Walter, ‘Complexity’: ‘Computational Complexity Theory’, The Stanford Encyclopedia of Philosophy, edited by Edward N. Zalta, Fall 2021, Metaphysics Research Lab, Stanford University, 2021. |
van Emde Boas, Peter, ‘Models’: ‘Machine models and simulations’, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, 1991, pp 1–66. |
Levesque, Hector J., ‘Complexity’: ‘Logic and the Complexity of Reasoning’, Journal of Philosophical Logic 17.4 (1988), pp 355–389, jstor: 30227050. |