8
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ Go away!! We CS profs make a living from teaching sophisticated algorithms, your suggestion would leave us without a job! $\endgroup$ – vonbrand Jan 6 '16 at 0:33
  • $\begingroup$ Well... what do you expect from AI then? $\endgroup$ – Optimiser Jan 6 '16 at 3:56
  • $\begingroup$ Bubble sort isn't a Boolean function. Worse, not all sorting algorithms are equivalent! For example, some are not stable. $\endgroup$ – Yuval Filmus Jan 6 '16 at 9:19
  • $\begingroup$ 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. $\endgroup$ – Optimiser Jan 6 '16 at 18:38
  • $\begingroup$ @YuvalFilmus surely returning a sorted array isn't easier than returning true or false $\endgroup$ – vonbrand Jan 6 '16 at 22:37
10
$\begingroup$

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.

$\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.