# Class of Algorithms where finding output of algorithm can be aided by output of same algorithm given a similar input

Sorry for the confusing title, but I'm trying to find out if a certain algorithm or class of algorithms fits this description. Given an algorithm A, computing A(x) can be computionally easier if A(g) is known, where g is close to x, and it's easier the closer g gets to x. So also, the amount of computation A has to do grows with respect to the size of the input.

You would also have to be able to calculate the output of A(x) given A(g), x-g, A(x-g). Does A exist for anything other than trivial artithemtic, and if so, is there an entire class of algorithms which A belongs to?

• Welcome to CS.SE! Can you edit the question to provide any context about your motivation for asking or how you'll use answers or to narrow down the question? This might help us provide answers that are more likely to be useful to you. I think there are many such algorithms (e.g., en.wikipedia.org/wiki/Dynamic_problem_(algorithms)), so it's hard to select just one.
– D.W.
Mar 6, 2017 at 20:54
• It seems that whenever you say algorithm, you really mean computational problem or function. Mar 6, 2017 at 21:05
• @YuvalFilmus I agreee; those terms are what I'm trying to say Mar 6, 2017 at 23:36
• What's the difference with dynamic programming? Mar 11, 2017 at 8:06
• Although the concept of dynamic programming is related, you seem to be describing recursive algorithms in general, since those algorithms will be faster if you have precomputed a 'close' value (depending on the definition of 'close'). As far as I know, all algorithms that compute computable functions can be described using recursion, so this is a very general class. So, I think you have to be more precise about your input domains (just integers, or something else?) and what 'close' means on the input. Mar 14, 2017 at 12:27

In complexity theory, a problem $A$ is called self-reducible, if a $A(x)$ can be computed easily when given the solutions to one or more subproblems $A(x')$ for inputs with $|x'| < |x|$ for free. What "easily" means depends on the context, in most cases it means "in polynomial time" in the context where $A$ is $\mathsf{NP}$-complete.
The standard example is $SAT$, where the problem of satisfiability of a formula $\varphi$ reduces to the same problem for the two formulas $\varphi[x:=0]$ and $\varphi[x:=1]$, which are smaller than $\varphi$ after simpification.