Relativization of the theory of computational complexity
Nancy Ann Lynch, Albert R. Meyer, Michael J. Fischer · Transactions of the American Mathematical Society · 1976
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.