3 ms·

I don't think that this is a sign that computer science lacks a decent unifying theoretical framework. We can even proof that there is no optimal sorting algor

I don't think that this is a sign that computer science lacks a decent unifying theoretical framework. We can even proof that there is no optimal sorting algorithm. "For every sorting algorithm x exists an input i for which an sorting algorithm y exists, so that y sorts i faster than x" is provable

klodolph 10y ago
Well, yes, but that's not terribly illuminating because your algorithm Y just has to encode the permutation for I and then check that the result is sorted before falling back to another algorithm. So in another sense you can say that this is true for any problem where the NTIME complexity is less than the DTIME complexity, which is an incredibly large set of problems, because you can just encode an oracle into your machine for a chosen input.
- LeanderK 10y ago
  well, a sorting algorithm has to sort arbitrary input, so def sort(ignore) = [1,2,3] does not count. The details are complicated and i am not sure if i am ready to understand the proof, but i think you can even proof that there is no optimal algorithm even when you rule out trivial things like checking if the input matches a given list and returning a pre-sorted one or else sort manually.
  - chriswarbo 10y ago
    Clearly, as you say, ignoring the input and producing a single output is not a sorting algorithm. Comparing the input against pre-defined lists with a generic fallback algorithm is a sorting algorithm, but as you say it's rather 'trivial'. However, I read klodolph's use of "permutation" as being more subtle than the above. Rather than splitting inputs into "known" (use pre-sorted answer) and "unknown" (use generic fallback), instead you write a valid sorting algorithm which treats all inputs in the same way, but you arrange all of the possible choice-points to perform optimally for your pre-selected inputs. For example, imagine a quicksort which chooses exactly the right "random" pivots for particular inputs. It's not hard-coded in a particularly 'trivial' way; the fact that it works optimally for those inputs is a (carefully engineered) 'coincidence'. In fact, some quicksort implementations randomly shuffle the input first, to lower the probability of malicious input triggering the worst-case O(n^2) behaviour. What if such a shuffle just-so-happend to "cancel out" the disorder of particular inputs, causing them to become sorted before the quicksort even begins? It's debatable whether that would count as a 'coincidence' or 'checking if the input matches a given list'. We could even avoid the O(log n) overheads of average-case quicksort if we used that shuffling trick with bubble sort, to get its O(n) best-case performance.
joe_the_user 10y ago
I think the GP was being sarcastic and casting doubt on the need for or importance of a unifying theoretical framework in CS. Which is a shame. I think there are unifying frameworks in CS but think we could use more and I think we would benefit if, when people looked at a body of knowledge and saw just a list of techniques, they would say "hey, this could benefit from a more unified treatment".
- LeanderK 10y ago
  well thats a typical case of editing without reading the answer if was referring to first. I read Andrews answer and then changed my comment without re-reading the answer i was referring to. I normally hate when this happens, so i have to apologise.

klodolph 10y ago

Well, yes, but that's not terribly illuminating because your algorithm Y just has to encode the permutation for I and then check that the result is sorted before falling back to another algorithm. So in another sense you can say that this is true for any problem where the NTIME complexity is less than the DTIME complexity, which is an incredibly large set of problems, because you can just encode an oracle into your machine for a chosen input.

LeanderK 10y ago
well, a sorting algorithm has to sort arbitrary input, so def sort(ignore) = [1,2,3] does not count. The details are complicated and i am not sure if i am ready to understand the proof, but i think you can even proof that there is no optimal algorithm even when you rule out trivial things like checking if the input matches a given list and returning a pre-sorted one or else sort manually.
- chriswarbo 10y ago
  Clearly, as you say, ignoring the input and producing a single output is not a sorting algorithm. Comparing the input against pre-defined lists with a generic fallback algorithm is a sorting algorithm, but as you say it's rather 'trivial'. However, I read klodolph's use of "permutation" as being more subtle than the above. Rather than splitting inputs into "known" (use pre-sorted answer) and "unknown" (use generic fallback), instead you write a valid sorting algorithm which treats all inputs in the same way, but you arrange all of the possible choice-points to perform optimally for your pre-selected inputs. For example, imagine a quicksort which chooses exactly the right "random" pivots for particular inputs. It's not hard-coded in a particularly 'trivial' way; the fact that it works optimally for those inputs is a (carefully engineered) 'coincidence'. In fact, some quicksort implementations randomly shuffle the input first, to lower the probability of malicious input triggering the worst-case O(n^2) behaviour. What if such a shuffle just-so-happend to "cancel out" the disorder of particular inputs, causing them to become sorted before the quicksort even begins? It's debatable whether that would count as a 'coincidence' or 'checking if the input matches a given list'. We could even avoid the O(log n) overheads of average-case quicksort if we used that shuffling trick with bubble sort, to get its O(n) best-case performance.

joe_the_user 10y ago

I think the GP was being sarcastic and casting doubt on the need for or importance of a unifying theoretical framework in CS. Which is a shame. I think there are unifying frameworks in CS but think we could use more and I think we would benefit if, when people looked at a body of knowledge and saw just a list of techniques, they would say "hey, this could benefit from a more unified treatment".

LeanderK 10y ago
well thats a typical case of editing without reading the answer if was referring to first. I read Andrews answer and then changed my comment without re-reading the answer i was referring to. I normally hate when this happens, so i have to apologise.