Relativization of the theory of computational complexity

Lynch, Nancy Ann; Meyer, Albert R.; Fischer, Michael J.

doi:10.1090/S0002-9947-1976-0403933-6

Relativization of the theory of computational complexity
HTML articles powered by AMS MathViewer

by Nancy Ann Lynch, Albert R. Meyer and Michael J. Fischer PDF

Trans. Amer. Math. Soc. 220 (1976), 243-287 Request permission

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

Paul Axt, On a subrecursive hierarchy and primitive recursive degrees, Trans. Amer. Math. Soc. 92 (1959), 85–105. MR 126377, DOI 10.1090/S0002-9947-1959-0126377-3
Manuel Blum, A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach. 14 (1967), 322–336. MR 235912, DOI 10.1145/321386.321395
Manuel Blum, On effective procedures for speeding up algorithms, J. Assoc. Comput. Mach. 18 (1971), 290–305. MR 290884, DOI 10.1145/321637.321648
A. Borodin, Computational complexity and the existence of complexity gaps, J. Assoc. Comput. Mach. 19 (1972), 158–174; corrigendum, ibid. 19 (1972), 576. MR 321355, DOI 10.1145/321679.321691
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
Robert L. Constable, The operator gap, J. Assoc. Comput. Mach. 19 (1972), 175–183. MR 314608, DOI 10.1145/321679.321692
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
J. Hartmanis and J. E. Hopcroft, An overview of the theory of computational complexity, J. Assoc. Comput. Mach. 18 (1971), 444–475. MR 288028, DOI 10.1145/321650.321661
Carl G. Jockusch Jr., Uniformly introreducible sets, J. Symbolic Logic 33 (1968), 521–536. MR 237330, DOI 10.2307/2271359
Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
Nancy Lynch, “Helping”: several formalizations, J. Symbolic Logic 40 (1975), no. 4, 555–566. MR 392524, DOI 10.2307/2271779
L. H. Landweber and E. L. Robertson, Recursive properties of abstract complexity classes, J. Assoc. Comput. Mach. 19 (1972), 296–308. MR 300875, DOI 10.1145/321694.321702
Michael Machtey, Augmented loop languages and classes of computable functions, J. Comput. System Sci. 6 (1972), 603–624. MR 406779, DOI 10.1016/S0022-0000(72)80032-1
Michael Machtey, Helping and the meet of pairs of honest subrecursive classes, Information and Control 28 (1975), 76–89. MR 375835

Classes of computable functions defined by bounds on computation

Albert R. Meyer and Patrick C. Fischer, Computational speed-up by effective operators, J. Symbolic Logic 37 (1972), 55–68. MR 317908, DOI 10.2307/2272545

Relatively complex recursive sets

35

Albert R. Meyer and Dennis M. Ritchie, A classification of the recursive functions, Z. Math. Logik Grundlagen Math. 18 (1972), 71–82. MR 295913, DOI 10.1002/malq.19720180405
R. Moll and A. R. Meyer, Honest bounds for complexity classes of recursive functions, J. Symbolic Logic 39 (1974), 127–138. MR 357084, DOI 10.2307/2272353
Charles Parsons, Hierarchies of primitive recursive functions, Z. Math. Logik Grundlagen Math. 14 (1968), 357–376. MR 238702, DOI 10.1002/malq.19680142106

Program structure and computational complexity

Robert W. Ritchie, Classes of predictably computable functions, Trans. Amer. Math. Soc. 106 (1963), 139–173. MR 158822, DOI 10.1090/S0002-9947-1963-0158822-2
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
Hartley Rogers Jr., Gödel numberings of partial recursive functions, J. Symbolic Logic 23 (1958), 331–341. MR 103821, DOI 10.2307/2964292
Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554

The extension of machine-independent computational complexity theory to oracle machine computation and to the computation of finite functions

B. A. Trahtenbrot, Autoreducibility, Dokl. Akad. Nauk SSSR 192 (1970), 1224–1227 (Russian). MR 0274287