# Size-limited oracles

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.

-
I suggest adding the tag computability-theory, since your question belongs to that subject more than complexity theory. You might also add lo.logic. – Joel David Hamkins Feb 26 '13 at 18:00
@Joel: Does it? I wouldn’t know about computability theory, but this concept has been certainly studied a lot in complexity. – Emil Jeřábek Feb 28 '13 at 15:45
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... – Joel David Hamkins Feb 28 '13 at 17:13

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 .
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. – Joel David Hamkins Feb 28 '13 at 17:05
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$.