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.



Size-limited oracles
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> .


