# Deformation of algorithms

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.

• Define what "deform" means and what makes one algorithm "better" than another, and off you go. I don't see a conceptual problem. Commented Oct 12, 2017 at 17:49
• Sure it's easy to deform an algorithm, but is there a way to do that such that you're solving the same problem.
– tom
Commented Oct 12, 2017 at 18:14
• 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! Commented Oct 12, 2017 at 18:21
• 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 Commented Oct 12, 2017 at 19:30
• "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.
– tom
Commented Oct 12, 2017 at 19:32

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}$).
• 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. Commented Oct 12, 2017 at 17:47