<p>Let us suppose we have a sort function.</p>
<p>One way of specifying it is to say that a sort function is any function where if the input/output are vectors <span class="math-container">$I, O$</span>, then <span class="math-container">$O_i \leq O_j \forall i &lt; j$</span> and for every element <span class="math-container">$e \in I$</span>, the count of <span class="math-container">$e$</span> in <span class="math-container">$I$</span> is the same as the count of <span class="math-container">$e$</span> in <span class="math-container">$O$</span>.</p>
<p>Another way is to say that a sort function is any function whose output matches the output of insertion sort on the same input.</p>
<p>However the latter specification relies on actually solving the search problem and using it to specify the decision problem (whether an input is sorted or not). Is there a way to formalize the difference between the two so I can only consider specifications of the former variety?</p>

CC BY-SA 4.0
2022-07-26T22:39:53.677Z
You could look at the computational complexity of the verification algorithm.
usul
CC BY-SA 4.0
2022-07-27T10:30:36.657Z
Or the descriptive (say, Kolmogorov) complexity of the specification.
Neal Young
CC BY-SA 4.0
2022-07-28T18:36:34.403Z
I am not completely sure what you are asking. Are you asking for a formal way to distinguish between different specifications of sorting functions?
Martin Berger
<cc.complexity-theory><pl.programming-languages>
Decision vs search problem specification
Opt
# Decision vs search problem specification

(Asked by: username_0 on 2022-07-25)

Let us suppose we have a sort function.

One way of specifying it is to say that a sort function is any function where if the input/output are vectors $I, O$, then $O\_i \leq O\_j \forall i < j$ and for every element $e \in I$, the count of $e$ in $I$ is the same as the count of $e$ in $O$.

Another way is to say that a sort function is any function whose output matches the output of insertion sort on the same input.

However the latter specification relies on actually solving the search problem and using it to specify the decision problem (whether an input is sorted or not). Is there a way to formalize the difference between the two so I can only consider specifications of the former variety?

**Tags:** cc.complexity-theory, pl.programming-languages

> **Comments:**
> **username_1**: You could look at the computational complexity of the verification algorithm.  
> **username_2**: Or the descriptive (say, Kolmogorov) complexity of the specification.  
> **username_3**: I am not completely sure what you are asking. Are you asking for a formal way to distinguish between different specifications of sorting functions?  

---

## 0 answers

