4
$\begingroup$

Has there been any attempt at a general theory to describe how an algorithm can be "deformed" to solve the problem more efficiently?

For example suppose we have an algorithm (say sorting a list of numbers) which solves the problem in $O(n^2)$. Can we deform this algorithm (in the "space of algorithms") to an algorithm which solves the problem in $O(n \log(n))$ time?

My motivation for asking this questions comes from analysis where if we want to solve the equation $f(x) = 0$ one technique is to first guess an $x_0$ such that $f(x_0)$ is small, then look in the neighborhood of that $x_0$ to find $x$.

Of course, I'm guessing the answers is no, but I'm sure a question similar to the above must have been posed somewhere in the literature somewhere.

$\endgroup$
7
  • 4
    $\begingroup$ Define what "deform" means and what makes one algorithm "better" than another, and off you go. I don't see a conceptual problem. $\endgroup$
    – Raphael ♦
    Oct 12, 2017 at 17:49
  • $\begingroup$ Sure it's easy to deform an algorithm, but is there a way to do that such that you're solving the same problem. $\endgroup$
    – tom
    Oct 12, 2017 at 18:14
  • $\begingroup$ That's easy, too, but transformations that obviously don't change the computed function are probably useless. That said, you just have to make correctness part of the fitness function! $\endgroup$
    – Raphael ♦
    Oct 12, 2017 at 18:21
  • $\begingroup$ Are you trying to do some sort of gradient descent on algorithms to improve it? For some specific class of "algorithms", we have this paper: Learning to learn without gradient descent by gradient descent $\endgroup$
    – justhalf
    Oct 12, 2017 at 19:30
  • $\begingroup$ "Are you trying to do some sort of gradient descent on algorithms to improve it?" Yes, that was my initial motivation for asking this question. $\endgroup$
    – tom
    Oct 12, 2017 at 19:32

1 Answer 1

Reset to default
11
$\begingroup$

There is no general way to do this. The "space of algorithms" is not a nice one, with a natural metric or other nice properties, unlike e.g. the real numbers. Note that even in the case of trying to solve $f(x)=0$, where your search space is $\mathbb{R}$, most algorithms work under several assumptions on $f$, e.g. continuity (there is no algorithm which can solve/approximate $f(x)=0$ for an arbitrary $f:\mathbb{R}\rightarrow\mathbb{R}$).

See the answers here, and also here for simple impossibility results regarding a general approach for optimizing the running time of an algorithm.

$\endgroup$
6
  • 3
    $\begingroup$ You could make a deformation metric over expressions of algorithms (which is different from algorithms: defining a metric that's invariant if you make tweaks to how the algorithm is defined would be a lot harder). But if you try to deform an algorithm, you'd almost always get one that does something different, so looking for equivalent algorithms that way would be very difficult and inefficient. $\endgroup$
    – Gilles 'SO- stop being evil'
    Oct 12, 2017 at 17:11
  • $\begingroup$ I'm not sure I agree in this generality. For a given problem $P$, there is are natural ways to define fitness functions for algorithms: number of correctly solved instances among a test set; number of machine steps taken on some test instances; etc. It also seems feasible to define small mutations of algorithms, if they are given in a formal language. In summary, we can certainly perform randomized searches in the space of all algorithms (of a certain class, maybe). Whether that's effective (let alone efficient) is highly doubtful, though. $\endgroup$
    – Raphael ♦
    Oct 12, 2017 at 17:47
  • $\begingroup$ There are (academic) tools, for instance, that find functions and correctness proofs for data types (in a functional language), basically by enumerating all programs and proofs. $\endgroup$
    – Raphael ♦
    Oct 12, 2017 at 17:48
  • 3
    $\begingroup$ @Ariel Certainly, it's uncomputable! $\endgroup$
    – Raphael ♦
    Oct 12, 2017 at 18:43
  • 1
    $\begingroup$ The "space of algorithms" quote made me want to ask if there's some category of complexity, but appears that is answered in the negative. $\endgroup$
    – BurnsBA
    Oct 13, 2017 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.