The Levesque–van Em Boas invariance thesis.

The invariance thesis (see Arora and Barak, § 1.3.1; Dean, § 2.2; van Emde Boas, § 1; Levesque, § 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 (§ 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.

Arora, Sanjeev and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge: Cambridge University Press, 2009.

Dean, Walter, ‘Computational Complexity Theory’, The Stanford Encyclopedia of Philosophy, ed. by Edward N. Zalta, Fall 2021, Metaphysics Research Lab, Stanford University, 2021.

Levesque, Hector J., ‘Logic and the Complexity of Reasoning’, Journal of Philosophical Logic 17.4 (1988), 355–389.

Van Emde Boas, Peter, ‘Machine models and simulations’, Handbook of theoretical computer science (vol. A): algorithms and complexity, Cambridge, MA, USA: MIT Press, 1991, 1–66.

À propos.

Étiquettes.

computational complexity, philo.

Mises à jour.

• J.P. Loo (12 juin 2025): Finished migration from joshualoo.net.
• J.P. Loo (28 mai 2025): Initial commit.