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 Free Access

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.

**[A]**Paul Axt,*On a subrecursive hierarchy and primitive recursive degrees*, Trans. Amer. Math. Soc.**92**(1959), 85–105. MR**0126377**, 10.1090/S0002-9947-1959-0126377-3**[B1]**Manuel Blum,*A machine-independent theory of the complexity of recursive functions.*, J. Assoc. Comput. Mach.**14**(1967), 322–336. MR**0235912****[B2]**Manuel Blum,*On effective procedures for speeding up algorithms*, J. Assoc. Comput. Mach.**18**(1971), 290–305. MR**0290884****[Bo]**A. Borodin,*Computational complexity and the existence of complexity gaps*, J. Assoc. Comput. Mach.**19**(1972), 158–174; corrigendum, ibid. 19 (1972), 576. MR**0321355****[C]**Alan Cobham,*The intrinsic computational difficulty of functions*, Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.), North-Holland, Amsterdam, 1965, pp. 24–30. MR**0207561****[Con]**Robert L. Constable,*The operator gap*, J. Assoc. Comput. Mach.**19**(1972), 175–183. MR**0314608****[D]**Martin Davis,*Computability and unsolvability*, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR**0124208****[HH]**J. Hartmanis and J. E. Hopcroft,*An overview of the theory of computational complexity*, J. Assoc. Comput. Mach.**18**(1971), 444–475. MR**0288028****[J]**Carl G. Jockusch Jr.,*Uniformly introreducible sets*, J. Symbolic Logic**33**(1968), 521–536. MR**0237330****[K]**Stephen Cole Kleene,*Introduction to metamathematics*, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR**0051790****[L]**Nancy Lynch,*“Helping”: several formalizations*, J. Symbolic Logic**40**(1975), no. 4, 555–566. MR**0392524****[LR]**L. H. Landweber and E. L. Robertson,*Recursive properties of abstract complexity classes*, J. Assoc. Comput. Mach.**19**(1972), 296–308. MR**0300875****[Ma1]**Michael Machtey, Private communication.**[Ma2]**Michael Machtey,*Augmented loop languages and classes of computable functions*, J. Comput. System Sci.**6**(1972), 603–624. Third Annual ACM Symposium on the Theory of Computing (Shaker Heights, Ohio, 1971). MR**0406779****[Ma3]**Michael Machtey,*Helping and the meet of pairs of honest subrecursive classes*, Information and Control**28**(1975), 76–89. MR**0375835****[McC]**Edward M. McCreight,*Classes of computable functions defined by bounds on computation*, Ph. D. Thesis, Department of Computer Science, Carnegie-Mellon University, July 1969.**[McCMe]**E. M. McCreight and A. R. Meyer,*Classes of computable functions defined by bounds on computation*, Sympos. on Theory of Computing, Marina del Rey, May 1969.**[MeF1]**Albert R. Meyer and Patrick C. Fischer,*Computational speed-up by effective operators*, J. Symbolic Logic**37**(1972), 55–68. MR**0317908****[MeF2]**Albert R. Meyer and Michael J. Fischer,*Relatively complex recursive sets*, J. Symbolic Logic**35**(1970), 607-608. (abstract).**[MeRd]**Albert R. Meyer and Dennis M. Ritchie,*A classification of the recursive functions*, Z. Math. Logik Grundlagen Math.**18**(1972), 71–82. MR**0295913****[MoMe]**R. Moll and A. R. Meyer,*Honest bounds for complexity classes of recursive functions*, J. Symbolic Logic**39**(1974), 127–138. MR**0357084****[Par]**Charles Parsons,*Hierarchies of primitive recursive functions*, Z. Math. Logik Grundlagen Math.**14**(1968), 357–376. MR**0238702****[RD]**Dennis M. Ritchie,*Program structure and computational complexity*, Ph. D. Thesis, Division of Engineering and Applied Physics, Harvard University, 1967.**[RRW]**Robert W. Ritchie,*Classes of predictably computable functions*, Trans. Amer. Math. Soc.**106**(1963), 139–173. MR**0158822**, 10.1090/S0002-9947-1963-0158822-2**[Ro1]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[Ro2]**Hartley Rogers Jr.,*Gödel numberings of partial recursive functions*, J. Symb. Logic**23**(1958), 331–341. MR**0103821****[Sa]**Gerald E. Sacks,*Degrees of unsolvability*, Princeton University Press, Princeton, N.J., 1963. MR**0186554****[Sy]**David M. Symes,*The extension of machine-independent computational complexity theory to oracle machine computation and to the computation of finite functions*, Ph. D. Thesis, Department of Applied Analysis and Computer Science, University of Waterloo, Oct. 1971.**[T1]**B. A. Trahtenbrot,*Autoreducibility*, Dokl. Akad. Nauk SSSR**192**(1970), 1224–1227 (Russian). MR**0274287****[T2]**-, Private communication.

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

DOI:
https://doi.org/10.1090/S0002-9947-1976-0403933-6

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