Relativization of the Theory of Computational Complexity
Abstract
Blum's machine-independent treatment of the complexity of partial recursive functions is extended to relative algorithms (as represented by Turing machines with oracles). The author proves relativeizations of several results of Blum complexity theory. A recursive relatedness theorem is proved, showing that any two relative complexity measures are related by a fixed recursive function. This theorem allows one to obtain proofs of results for all measures from proofs for a particular measure. The author studies complexity-determined reducibilities, the parallel notion to complexity classes for the relativized case. Truth-table and primitive recursive reducibilities are reducibilities of this type. The concept of a set helping the computation of a function is formalized. Basic properties of the helping relation are proved, including non- transitivity and bounds on the amount of help certain sets can provide.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1972
- Accession Number
- AD0744032
Entities
People
- Nancy Lynch
Organizations
- Massachusetts Institute of Technology