Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-17T03:58:11.971Z Has data issue: false hasContentIssue false

On complexity properties of recursively enumerable sets1

Published online by Cambridge University Press:  12 March 2014

M. Blum
Affiliation:
University of California, Berkeley, California 94720
I. Marques
Affiliation:
Núcleo de Computaçāo Eletrônica and Coppe, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil

Extract

An important goal of complexity theory, as we see it, is to characterize those partial recursive functions and recursively enumerable sets having some given complexity properties, and to do so in terms which do not involve the notion of complexity.

As a contribution to this goal, we provide characterizations of the effectively speedable, speedable and levelable [2] sets in purely recursive theoretic terms. We introduce the notion of subcreativeness and show that every program for computing a partial recursive function f can be effectively speeded up on infinitely many integers if and only if the graph of f is subcreative.

In addition, in order to cast some light on the concepts of effectively speedable, speedable and levelable sets we show that all maximal sets are levelable (and hence speedable) but not effectively speedable and we exhibit a set which is not levelable in a very strong sense but yet is effectively speedable.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1973

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