2
$\begingroup$

It is straightforward enough to analyze the complexity of a particular algorithm as a function of input size or other variables in terms of runtime or space used or whatever else. I am wondering if anyone has researched the complexity of producing the algorithm itself. For example, if I have implemented a merge sort, I can quickly say that the run time is O(n log n), but suppose my input were actually something like "Your input will be a list of elements and a transitive, antisymmetric comparison operator. Output a list of those same elements in sorted order." Without already knowing a sorting algorithm, what is the complexity of producing an algorithm that meets those requirements and runs in O(n log n) time?

$\endgroup$
  • 3
    $\begingroup$ It's not clear to me at all how this is formalized. I think your question needs more details. $\endgroup$ – Sasho Nikolov Jul 17 at 17:31
  • 5
    $\begingroup$ I interpret your question as of the form "given a formal problem specification, produce an efficient algorithm for the problem". To what extent this is possible will depend on what kind of specification you have, and what kinds of algorithms you allow. E.g., one way could be "given the code for one algorithm (thereby defining a problem), find an algorithm that is equivalent (gives the same output for each input) but optimally efficient." In that form, the problem is easily seen to be undecidable. $\endgroup$ – Neal Young Jul 17 at 23:12
  • 1
    $\begingroup$ This is the “synthesis” of programs from a given specification. It’s a huge and important research area, I’m not sure why this question for downvoted. Btw, decidability and complexity of the problem depends on the language used for specifications (as @NealYoung mentioned). $\endgroup$ – gigabytes Jul 20 at 8:46
  • $\begingroup$ On the other hand, the kind of “output program” you produce (e.g. finite automata) will generally give you an upper bound on the complexity of the result. $\endgroup$ – gigabytes Jul 20 at 8:48
  • 1
    $\begingroup$ Yes, I suppose. Although It's quite difficult to know what to search without the right keywords. The word "synthesis" does not appear in the question. Looking for "producing an algorithm" would not be very successful... It seems like the OP comes from a totally different background and does not even know if the question makes sense. CS is very broad, this can happen. Anyway, whether or not this is ground for down-voting depends on the site's policy, which I do not want to criticize, but It would be nice and educational to explain the down votes in comment, maybe? I was planning to answer, btw $\endgroup$ – gigabytes Jul 26 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.