Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Relativization of the theory of computational complexity

Authors: Nancy Ann Lynch, Albert R. Meyer and Michael J. Fischer
Journal: Trans. Amer. Math. Soc. 220 (1976), 243-287
MSC: Primary 02F25; Secondary 68A20, 02F10
MathSciNet review: 0403933
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The axiomatic treatment of the computational complexity of partial recursive functions initiated by Blum is extended to relatively computable functions (as computed, for example, by Turing machines with oracles). Relativizations of several results of complexity theory are carried out. A recursive relatedness theorem is proved, showing that any two relative complexity measures are related by a fixed recursive function. This theorem allows proofs of results for all measures to be obtained from proofs for a particular measure.

Complexity-determined reducibilities are studied. Truth-table and primitive recursive reducibilities are proved to be reducibilities of this type.

The concept of a set ``helping'' the computation of a function (by causing a saving in resource when used as an oracle in the computation of the function) is formalized. Basic properties of the helping relation are given, including nontransitivity and bounds on the amount of help certain sets can provide.

Several independence results (results about sets that do not help each other's computation) are proved; they are subrecursive analogs to degrees-of-unsolvability theorems with proofs using diagonalization and priority arguments. In particular, the existence of a ``universally-helped set'' is discussed; partial results are obtained in both directions. The deepest result in the paper is a finite-injury priority argument (without an apparent recursive bound on the number of injuries) which produces sets preserving an arbitrary lower bound on the complexity of any given set.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02F25, 68A20, 02F10

Retrieve articles in all journals with MSC: 02F25, 68A20, 02F10

Additional Information

Keywords: Complexity theory, Blum measure, relative algorithm, oracle Turing machine, relativization, reducibility, helping, diagonalization, priority argument, convergence argument
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society