Are all problems in the same time hierarchy related to each other? In this problem, &quot;runtimes&quot; refer to worst-case complexity compared up to constant factor.
Say you have two problems, A and B, in the same time hierarchy, and it is clear that algorithm P solves A with that time complexity.
Suppose an oracle spits out the result of problem A using algorithm P. Then does problem B, with the help of this oracle (call this B^P), necessarily have an algorithm running in less time than problem B without the oracle?
If problem A is complete for the class, the class is higher than P, and problem B cannot be solved in polynomial time, then yes, there is some polynomial algorithm that makes use of the oracle and solves the problem.
By definition, if a problem A is complete for some class C, then every problem of this class is reducible in polynomial time to this problem. As a result, a polynomial algorithm for a problem B given an oracle P of the (complete for the class) problem A (we assume that the oracle spits out the answer to an instance of A in constant time) is the following:
Input: instance of problem B

Reduce the instance of B to an instance of A (polytime)
Answer the obtained instance of A using P (constant time)

However, it is not always easy to find the reduction from one problem to another in the same class.