<p>Is there a lower bound for comparison sorting where the comparison function is supplied as the encoding of a Turing machine, rather than being available as an oracle?</p>
<p>A bit more formally, let's say that a Turing machine <span class="math-container">$C$</span> implements a relation <span class="math-container">$R$</span> if, given any <span class="math-container">$x, y \in \{0,1\}^*$</span>, <span class="math-container">$C$</span> halts on the input <span class="math-container">$\langle x, y \rangle$</span>, and it accepts if and only if <span class="math-container">$xRy$</span>.</p>
<p>Now, let's say that a Turing machine <span class="math-container">$S$</span> implements a sorting function if, when running on an input <span class="math-container">$\langle C, \vec{x}\rangle$</span>, where <span class="math-container">$C$</span> is the encoding of some Turing machine that implements a preorder relation <span class="math-container">$R$</span> (i.e., a symmetric and transitive relation), and <span class="math-container">$\vec{x}$</span> is a sequence of bit strings, then <span class="math-container">$S$</span> halts, and its output is the list of elements of <span class="math-container">$\vec{x}$</span> sorted according to <span class="math-container">$R$</span>.  If the input of <span class="math-container">$S$</span> is not of this form, then its behavior can be arbitrary (even running forever).</p>
<p>Is there a useful lower bound for the running time of such an <span class="math-container">$S$</span>? Note that I am <em>not</em> assuming that <span class="math-container">$S$</span> can call <span class="math-container">$C$</span> as an oracle; it needs to simulate it explicitly. Since <span class="math-container">$C$</span> could have arbitrary complexity, this lower bound is only interesting if it can mention <span class="math-container">$C$</span> as well. For example, it would be nice if we could say that the run time of this machine is <span class="math-container">$\Omega (k_C(n) \cdot n \log n)$</span>, where <span class="math-container">$n$</span> is the size of the bit string representation of the list <span class="math-container">$\vec{x}$</span>, and <span class="math-container">$k_C(n)$</span> is the maximum time required by <span class="math-container">$C$</span> to compare strings of size at most <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2024-10-23T06:15:03.143Z
You can obviously reduce an arbitrary computable language to this problem, hence you get as large computable lower bounds as you wish. What am I missing?
Emil Jeřábek
CC BY-SA 4.0
2024-10-23T15:03:39.573Z
@EmilJeřábek If the lower bound is only allowed to mention the size of the input $\langle C, \vec{x} \rangle$, then it can indeed be arbitrarily large. But I was hoping to find something interesting if the lower bound could mention the complexity of running $C$ as well. I added a clarification to the question.
Arthur Azevedo De Amorim
CC BY-SA 4.0
2024-10-24T02:35:07.580Z
Any particular reason to only want R (computed by C) to be a pre-order? Why not have R be a total pre-order or even a total order?
Joshua Grochow
CC BY-SA 4.0
2024-10-24T05:52:41.170Z
Please don't use "Edit" and append some stuff.  Instead, revise the question to what it should have been from the start, i.e., to make it read well for someone who encounters it for the first time.  See https://cs.meta.stackexchange.com/q/657/755
D.W.
CC BY-SA 4.0
2024-10-24T13:57:47.137Z
@JoshuaGrochow No particular reason. If restricting to a partial or total order simplifies the problem, I'd be interested as well.
Arthur Azevedo De Amorim
<time-complexity><lower-bounds><sorting>
Lower bound for comparison sort without oracle
Arthur Azevedo De Amorim
# Lower bound for comparison sort without oracle

(Asked by: username_0 on 2024-10-23)

Is there a lower bound for comparison sorting where the comparison function is supplied as the encoding of a Turing machine, rather than being available as an oracle?

A bit more formally, let's say that a Turing machine $C$ implements a relation $R$ if, given any $x, y \in \{0,1\}^\*$, $C$ halts on the input $\langle x, y \rangle$, and it accepts if and only if $xRy$.

Now, let's say that a Turing machine $S$ implements a sorting function if, when running on an input $\langle C, \vec{x}\rangle$, where $C$ is the encoding of some Turing machine that implements a preorder relation $R$ (i.e., a symmetric and transitive relation), and $\vec{x}$ is a sequence of bit strings, then $S$ halts, and its output is the list of elements of $\vec{x}$ sorted according to $R$. If the input of $S$ is not of this form, then its behavior can be arbitrary (even running forever).

Is there a useful lower bound for the running time of such an $S$? Note that I am *not* assuming that $S$ can call $C$ as an oracle; it needs to simulate it explicitly. Since $C$ could have arbitrary complexity, this lower bound is only interesting if it can mention $C$ as well. For example, it would be nice if we could say that the run time of this machine is $\Omega (k\_C(n) \cdot n \log n)$, where $n$ is the size of the bit string representation of the list $\vec{x}$, and $k\_C(n)$ is the maximum time required by $C$ to compare strings of size at most $n$.

**Tags:** time-complexity, lower-bounds, sorting
> **Comments:**
> **username_1**: You can obviously reduce an arbitrary computable language to this problem, hence you get as large computable lower bounds as you wish. What am I missing?  
> **username_0**: @EmilJeřábek If the lower bound is only allowed to mention the size of the input $\langle C, \vec{x} \rangle$, then it can indeed be arbitrarily large. But I was hoping to find something interesting if the lower bound could mention the complexity of running $C$ as well. I added a clarification to the question.  
> **username_2**: Any particular reason to only want R (computed by C) to be a pre-order? Why not have R be a total pre-order or even a total order?  
> **username_3**: Please don't use "Edit" and append some stuff.  Instead, revise the question to what it should have been from the start, i.e., to make it read well for someone who encounters it for the first time.  See https://cs.meta.stackexchange.com/q/657/755  
> **username_0**: @JoshuaGrochow No particular reason. If restricting to a partial or total order simplifies the problem, I'd be interested as well.  

---

## 0 answers

