3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 6 '17 at 20:54
  • 3
    $\begingroup$ It seems that whenever you say algorithm, you really mean computational problem or function. $\endgroup$ – Yuval Filmus Mar 6 '17 at 21:05
  • $\begingroup$ @YuvalFilmus I agreee; those terms are what I'm trying to say $\endgroup$ – Michael Mar 6 '17 at 23:36
  • $\begingroup$ What's the difference with dynamic programming? $\endgroup$ – Albert Hendriks Mar 11 '17 at 8:06
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Mar 14 '17 at 12:27
1
$\begingroup$

It can be algorithms which use initial guess, for example algorithms for finding roots and local minimums/maximum like Newton's method and gradient descend. Here g and x are functions, and g is close to x means that they have roots or local minimums/maximums in similar locations, so taking A(g) as initial guess, algorithm can converge faster to A(x).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\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.