<p>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 <strong>some</strong> polynomial algorithm that makes use of the oracle and solves the problem.</p>
<p>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:</p>
<p>Input: instance of problem B</p>
<ol>
<li>Reduce the instance of B to an instance of A (polytime)</li>
<li>Answer the obtained instance of A using P (constant time)</li>
</ol>
<p>However, it is not always <strong>easy</strong> to find the reduction from one problem to another in the same class.</p>

CC BY-SA 4.0
2020-12-15T18:29:34.487Z
2020-12-15T18:29:34.487Z
Pavlos M.
<p>In this problem, &quot;runtimes&quot; refer to worst-case complexity compared up to constant factor.</p>
<p>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.</p>
<p>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?</p>

CC BY-SA 4.0
2020-12-14T21:44:36.630Z
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.
Michael Wehar
CC BY-SA 4.0
2020-12-18T03:41:09.990Z
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.
Sariel Har-Peled
CC BY-SA 4.0
2021-05-14T20:19:56.193Z
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?
Neal Young
CC BY-SA 4.0
2021-09-12T03:18:03.400Z
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.
Joshua Grochow
<time-complexity><oracles><time-hierarchy>
Are all problems in the same time hierarchy related to each other?
chxu
# Are all problems in the same time hierarchy related to each other?

(Asked by: username_0 on 2020-12-14)

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?

**Tags:** time-complexity, oracles, time-hierarchy

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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?  
> **username_4**: 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.  

---

## 1 answers

### Answer by username_5 on 2020-12-15. Score: -2

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

1. Reduce the instance of B to an instance of A (polytime)
2. 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.


---

