Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T16:20:29.117Z Has data issue: false hasContentIssue false

Diversity of speed-ups and embeddability in computational complexity1

Published online by Cambridge University Press:  12 March 2014

Donald A. Alton*
Affiliation:
University of Iowa, Iowa City, Iowa 52242

Extract

The theory of computational complexity deals with those functions which can be computed subject to certain restrictions on the resources (for instance, time or memory) available for computation. Blum [5] gave an axiomatic characterization of some of the properties which should be possessed by a measure of computational complexity and established the existence of speed-upable functions—computable functions which fail to possess optimal programs in a particularly strong sense. Recursion theorists tend to like such functions, and people concerned with the specifics of real computing tend to consider such functions somewhat pathological. In Theorem 2 we show that such pathology is rampant: there is a great diversity of behavior among the collections of “run-times” of different functions which do not possess optimal programs, where such diversity is gauged by certain algebraic criteria which have computational significance. Roughly speaking, these algebraic criteria concern the ways in which various functions can be intermixed to satisfy requirements that certain functions can or cannot be computed more easily than certain other functions. (More detailed motivation for the relevance of these algebraic notions is given later.) Specifically, in Theorem 2 we generalize the embeddability theorem of McCreight and Meyer [12] (discussed below) by making speed-upable functions responsible for the embedding.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1976

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable