2
$\begingroup$

I am interested in complexity of algorithms which have access to the following peculiar sort of oracle:

Suppose that an invocation of an algorithm f with an input of size n has access to an oracle for f which works only when given input of size n/2 or less. For definiteness, let's say that f(x) for x less than n/2 can be computed in constant time and that calling the oracle with x greater than n/2 halts -- I want to avoid algorithms which call the oracle unless they are certain that the input they provide is sufficiently small.

Has anybody discussed such oracles? Obviously the effect is dramatic; for instance, if writing an algorithm to sum a sequence of numbers, access to such an oracle makes the entire computation constant time, by breaking the list into two sublists. I'm interested in the effect on more complicated problems, though, which may or may not decompose so easily.

Improve this question
$\endgroup$
3
  • $\begingroup$ I suggest adding the tag computability-theory, since your question belongs to that subject more than complexity theory. You might also add lo.logic. $\endgroup$
    – Joel David Hamkins
    Commented Feb 26, 2013 at 18:00
  • $\begingroup$ @Joel: Does it? I wouldn’t know about computability theory, but this concept has been certainly studied a lot in complexity. $\endgroup$
    – Emil Jeřábek
    Commented Feb 28, 2013 at 15:45
  • $\begingroup$ Emil, I think we have different concepts of the question, and I agree with you for your version. And the OP evidently also agrees with your version... $\endgroup$
    – Joel David Hamkins
    Commented Feb 28, 2013 at 17:13

2 Answers 2

Reset to default
3
$\begingroup$

Computational problems that can be efficiently (i.e., polynomial-time) computed from solutions of the problem on shorter instances are known as (downward) self-reducible. A classical example is SAT: given a CNF $\phi$ in variables $x_0,\dots,x_n$, let $\phi_0$ and $\phi_1$ be the CNFs in variables $x_0,\dots,x_{n-1}$ obtained by setting $x_n$ to 0 or 1 (respectively), and simplifying the formula accordingly. Then $\phi$ is satisfiable iff $\phi_0$ or $\phi_1$ is satisfiable. For a discussion of the self-reducibility phenomenon and pointers to the literature, see e.g. ftp://ftp.cs.rutgers.edu/cs/pub/allender/cie.plenary.pdf or http://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/selke-ma.pdf .

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is extremely helpful -- it appears that what I want is a special case of this notion of self-reducibility which restricts the shorter instances more tightly (relative to the starting problem) than just by constants, as in your example of SAT. Thanks for the links. $\endgroup$
    – Micah Blake McCurdy
    Commented Feb 28, 2013 at 16:55
  • $\begingroup$ Emil, you have a different conception than what I had taken the OP to describe. It seemed to me that he was trying to describe a machine equipped with an oracle $A$, but on input $x$ the only access to the oracle allowed was up to $|x|/2$. This is not the same as your situation, since there is no reason on his model to expect that $A$ itself is decidable by such machines. Indeed, if $A$ is not computable, then it couldn't be $A$-decidable in this way, since otherwise we could recursively compute all values of $A$ by reference to smaller values. $\endgroup$
    – Joel David Hamkins
    Commented Feb 28, 2013 at 17:05
1
$\begingroup$

Although I also find your concept interesting, the class of functions you get by this notion of computability will not be closed under composition. To see this, suppose that we have a noncomputable oracle $A$ consisting only of even natural numbers. The characteristic function of $A$ will not be $A$-computable using your notion, since if we could generate all information about $A$ from earlier information about $A$, then $A$ would be computable, contrary to assumption. But the function $n\mapsto 2n$ is computable, and the function $2n\mapsto 1$ if $n\in A$, otherwise $0$, is $A$-computable under your concept (if I have understood it correctly), but the composition of these functions would decide $A$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ While I don't disagree with your comment, I don't know how much I care about the fact that my notion doesn't form a class of functions closed under composition -- maybe this cavalier-ness outs me as not really a complexity theorist at all (which I'm not). The real motivation is to focus on decomposition algorithms, and I want some way of focussing on the complexity of the decomposition of the problem, without being distracted by the complexity of the problem being decomposed; except, of course, that I realize that not all problems are so easily decomposed and I want this to show up. $\endgroup$
    – Micah Blake McCurdy
    Commented Feb 28, 2013 at 14:00
  • $\begingroup$ My view is that because the class of functions computable by your devices is not closed under composition, it is debatable whether you really have a notion of computability at all. The counterargument to this, of course, would be that even in complexity theory, we consider, say, levels of the polynomial time hierarchy, which also are not closed under composition. But the genuine notion of computability in the background there is polynomial-time computability, which of course is closed under composition. $\endgroup$
    – Joel David Hamkins
    Commented Feb 28, 2013 at 14:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .