Relativization of the Theory of Computational Complexity
MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC
Pagination or Media Count:
Blums 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.
- Theoretical Mathematics