<p>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?</p>

CC BY-SA 4.0
2019-07-17T17:31:02.547Z
It's not clear to me at all how this is formalized. I think your question needs more details.
Sasho Nikolov
CC BY-SA 4.0
2019-07-17T23:12:28.227Z
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.
Neal Young
CC BY-SA 4.0
2019-07-20T08:46:53.683Z
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).
Nicola Gigante
CC BY-SA 4.0
2019-07-20T08:48:23.863Z
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.
Nicola Gigante
CC BY-SA 4.0
2019-07-26T10:23:18.927Z
@gigabytes: If somebody asks a question "has anybody looked at" when the question is about a "huge and important research area" of computer science, I would say this indicates a lack of research. Maybe grounds for down-voting?
Peter Shor 
CC BY-SA 4.0
2019-07-26T10:31:24.543Z
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
Nicola Gigante
<cc.complexity-theory><analysis-of-algorithms>
Is there any research on the complexity of producing given a problem description?
Joel Croteau
# Is there any research on the complexity of producing given a problem description?

(Asked by: username_0 on 2019-07-17)

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?

**Tags:** cc.complexity-theory, analysis-of-algorithms
> **Comments:**
> **username_1**: It's not clear to me at all how this is formalized. I think your question needs more details.  
> **username_2**: 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.  
> **username_3**: 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).  
> **username_3**: 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.  
> **username_4**: @gigabytes: If somebody asks a question "has anybody looked at" when the question is about a "huge and important research area" of computer science, I would say this indicates a lack of research. Maybe grounds for down-voting?  
> **username_3**: 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  

---

## 0 answers

