5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Dec 14 '20 at 21:44
  • 3
    $\begingroup$ 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. $\endgroup$ Dec 18 '20 at 3:41
  • 1
    $\begingroup$ 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? $\endgroup$
    – Neal Young
    May 14 at 20:19
  • $\begingroup$ 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. $\endgroup$ Sep 12 at 3:18
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.