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?

  • $\begingroup$ You could look at the computational complexity of the verification algorithm. $\endgroup$
    – usul
    Jul 26 at 22:39
  • $\begingroup$ Or the descriptive (say, Kolmogorov) complexity of the specification. $\endgroup$
    – Neal Young
    Jul 27 at 10:30
  • $\begingroup$ I am not completely sure what you are asking. Are you asking for a formal way to distinguish between different specifications of sorting functions? $\endgroup$ Jul 28 at 18:36


Your Answer

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