# Are all problems in the same time hierarchy related to each other?

In this problem, "runtimes" 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?

• I don't have an answer, but I have been wondering about this too. It seems that all Tally languages in $DTIME(n^{k+1}) \backslash DTIME(n^k)$ should be strictly easier than some non-Tally language in $DTIME(n^{k+1}) \backslash DTIME(n^k)$, but I am not sure if we can formally prove this. Dec 14 '20 at 21:44
• That seems probably wrong in P (or at least widely open). There are many problems that are believed for example to require quadratic time but we do not know if they are equivalent (and tit is a major open problem if they are [as far as I understand fine grained complexity). The classical example would be edit distance and some quadratic 3sum hard problem. Dec 18 '20 at 3:41
• For this question as stated, the answer clearly seems to be "no, it's not necessary". E.g. suppose B is, given n bits, are there an odd number of 1's? This seems to take linear time with or without an oracle for any other problem. Also, I don't understand what role the algorithm P plays here. Assuming calls to the oracle for A are not counted in the time for solving B, why does it matter how A is solved? OP, can you clarify your question? May 14 '21 at 20:19
• I think the answer is no. More specifically, I think one can modify the proof of the Time Hierarchy Thm to build two sets $A,B$ simultaneously such that $A \in \mathsf{DTIME}(f(n)) \backslash \mathsf{DTIME}^B(o(f(n)/\log f(n)))$ and $B \in \mathsf{DTIME}(f(n)) \backslash \mathsf{DTIME}^A(o(f(n)/\log f(n)))$. Might need $f$ to be a little big (maybe $2^n$), but maybe not - maybe one can do this under the same assumptions as the Time Hierarchy Thm. I'd have to write down the details to see, but don't have the time rn. Sep 12 '21 at 3:18