Relativization of the theory of computational complexity
Relativization of the theory of computational complexity
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 …