# 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. – Raphael Oct 12 '17 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 Oct 12 '17 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! – Raphael Oct 12 '17 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 – justhalf Oct 12 '17 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 Oct 12 '17 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. – Raphael Oct 12 '17 at 17:47