Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T19:27:28.522Z Has data issue: false hasContentIssue false

Recursively enumerable complexity sequences and measure independence

Published online by Cambridge University Press:  12 March 2014

Victor L. Bennison*
Affiliation:
Bell Laboratories, Naperville, Illinois 60540

Extract

Though researchers in the field of abstract computational complexity theory have utilized many of the tools of recursive function theory in the development of their field, the early results obtained (e.g., see [8]) seemed to be rather independent of results in recursion theory (at least to the extent that the results were not uniformly interesting to both varieties of theorists). It seems to have been generally accepted, however, that strong parallels of one form or another must exist between the two fields. Indeed, recent results of Blum and Marques [7], Morris [13], Soare [15] and Bennison [1], [3] have revealed a striking correspondence between complexity theoretic properties and recursion theoretic properties. These results are not contrived, but rather link together interesting properties which had arisen naturally and independently in their respective fields. This paper presents the results of research aimed at finding a recursion theoretic characterization for a complexity theoretic property which had arisen from the study of the speed-up phenomenon.

In abstract computational complexity theory we are concerned with categorizing computable functions or sets according to their relative difficulty of computation. The phrase “difficult to compute” may take on different meanings depending on which criteria (complexity theoretic properties) we use to define what it means for a function or set to be hard to compute. In the abstract setting, however, such criteria should yield the same classes of functions or sets regardless of the underlying abstract complexity measure (in the sense of Blum [4], e.g., tape, time, etc.). In other words, such criteria should be measure-independent. In this paper we will be considering one way of defining “difficult to compute”. Namely, we shall say that a function or set is difficult to compute if it does not have a recursively enumerable complexity sequence as defined by Meyer and Fischer [12]. For a property to have a recursion theoretic characterization it must be measure-independent, for a recursion theoretic property is, by its very nature, measure-independent. It will not be immediately obvious whether or not the property of having an r.e. complexity sequence is measure-independent. We attack this question by first considering an alternative definition of an r.e. complexity sequence, one which is easily seen to be measure-independent.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1980

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