Is there an algorithm for algorithms time/space complexity optimisation?

Question

In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of algorithms?

For example an implementation of bubble sort as an input for such an algorithm would produce an implementation of a sorting algorithm with time complexity closer to $O(n\log n)$.

• vonbrand: Go away!! We CS profs make a living from teaching sophisticated algorithms, your suggestion would leave us without a job!
• Optimiser: Well... what do you expect from AI then?
• Yuval Filmus: Bubble sort isn't a Boolean function. Worse, not all sorting algorithms are equivalent! For example, some are not stable.
• Optimiser: You are quite right but bubble sort and "good sort" is just an example of what I see as input and output, let's not concentrate on details.
• vonbrand: @YuvalFilmus surely returning a sorted array isn't easier than returning true or false

Answer 1

Look up Blum's speedup theorem (yes, this article is less than informative; look at a book on complexity theory). It essentially says that there are programs for which there is a program doing the same job that is faster by any specified margin for almost all input data.

By Rice's theorem, it is impossible to know if two given programs do the same job.

Yes, for some very restricted notions of "program", given an example one can construct the "best possible" program for the job. Important classes, even. But a very far cry from anything which is able to express bubblesort.