<p>This is not a full answer, but some partial pieces of information (which you might already be aware of).</p>
<hr />
<p>This is related to the number of linear extensions of the poset. It is known that the worst-case number of comparisons needed to sort a poset <span class="math-container">$P$</span> is between <span class="math-container">$\log_2 e(P)$</span> and <span class="math-container">$\log_{2}\left(\frac{11}{3}\right)\log_2 e(P)$</span> (<span class="math-container">$\approx 1.874\log_2 e(P)$</span>) , where <span class="math-container">$e(P)$</span> is the number of linear extensions of <span class="math-container">$P$</span>. The lower bound is easy, the upper bound follows from a relaxation of the 1/3–2/3 conjecture proven in [1].</p>
<p>Counting the number of linear extensions is <span class="math-container">$\#P$</span>-hard, but there are fully polynomial-time randomized approximation schemes for it, so you can approximate the worst-case number of comparisions needed within a factor of <span class="math-container">$(1+\epsilon)\log_{2}\left(\frac{11}{3}\right)$</span> in randomized polynomial time.</p>
<p>You can also approximate within a factor of <span class="math-container">$9.82$</span> in deterministic polynomial time [3, top row of Table 1].</p>
<p>I guess you might be able to find more relevant stuff by searching for &quot;sorting under partial information&quot; or looking at papers which cite or are cited in the ones I mentioned.</p>
<p>[1] <em>Kahn, Jeff; Saks, Michael</em>, <a href="https://doi.org/10.1007/BF00565647" rel="nofollow noreferrer"><strong>Balancing poset extensions</strong></a>, Order 1, 113-126 (1984). <a href="https://zbmath.org/?q=an:0561.06004" rel="nofollow noreferrer">ZBL0561.06004</a>.</p>
<p>[2] <em>Brightwell, Graham; Winkler, Peter</em>, <a href="https://doi.org/10.1007/BF00383444" rel="nofollow noreferrer"><strong>Counting linear extensions</strong></a>, Order 8, No. 3, 225-242 (1991). <a href="https://zbmath.org/?q=an:0759.06001" rel="nofollow noreferrer">ZBL0759.06001</a>.</p>
<p>[3] <em>Cardinal, Jean; Fiorini, Samuel; Joret, Gwenaël; Jungers, Raphaël M.; Munro, J. Ian</em>, <a href="https://arxiv.org/abs/0911.0086" rel="nofollow noreferrer"><strong>Sorting under partial information (without the ellipsoid algorithm).</strong></a>, Combinatorica 33, No. 6, 655-697 (2013). <a href="https://zbmath.org/?q=an:1315.06002" rel="nofollow noreferrer">ZBL1315.06002</a>.</p>

CC BY-SA 4.0
2024-02-10T16:01:43.063Z
Thanks, but indeed I was aware of these and I don't see why they would help in answering my question.
domotorp
CC BY-SA 4.0
2024-02-10T16:16:44.337Z
@domotorp I suspected. Still, I thought this was relevant information (it places some kind of upper bound on the optimization problem) and too long for a comment.
Tassle
CC BY-SA 4.0
2024-02-10T14:29:03.817Z
2024-02-10T14:29:03.817Z
Tassle
<p>SORTING problem.<br />
Input: A poset which corresponds to a partially sorted list of different numbers.<br />
Output: Number of pairwise comparisons needed (in the worst case) to get a completely sorted array.<br />
Is SORTING NP-hard?<br />
Is it NP-complete to decide whether less than <span class="math-container">$k$</span> comparisons are enough to finish?</p>
<p>Surprisingly, I couldn't find anything about this problem.</p>

CC BY-SA 4.0
2024-02-05T10:07:45.560Z
You probably know this as you have another post on this problem but if you impose zero conditions on the order (i.e. all elements are free to ordered in any way) then your question becomes "can we sort n elements using only k comparisons?" which has been studied without as listed in your other post…
Louis
CC BY-SA 4.0
2024-02-05T10:10:08.817Z
Why do you ask for NP? The problem clearly is in PSPACE, but do you have any intuition why it would be in NP?
Louis
CC BY-SA 4.0
2024-02-05T10:49:22.350Z
That is a good point, I haven't realized that. It could very well be PSPACE-complete, after all, this is like a 2-player game.
domotorp
CC BY-SA 4.0
2024-02-05T21:30:04.850Z
Possibly related: https://cstheory.stackexchange.com/q/53874/8237
Neal Young
CC BY-SA 4.0
2024-02-05T22:08:17.703Z
Also an old related question of mine: https://cs.stackexchange.com/questions/60807/is-greedy-minimax-permutation-rejecting-sorting-optimal
orlp
CC BY-SA 4.0
2024-02-06T05:36:15.910Z
@Neal I think that the problem you link to is quite different. There we know the values, so it is a full information game, and we want to count the swaps. Here we do not count swaps, but queries.
domotorp
CC BY-SA 4.0
2024-02-06T11:57:38.300Z
Yes, I agree.  Nonetheless I had some vague hope that one might do a reduction from that problem to yours.
Neal Young
CC BY-SA 4.0
2024-02-08T16:46:09.707Z
Would not the worst case be dependent on an algorithm?
rus9384
CC BY-SA 4.0
2024-02-08T19:38:52.133Z
@rus9384 Yes, it would.
domotorp
CC BY-SA 4.0
2024-02-08T22:42:10.333Z
Is the algorithm a part of the input/fixed or should we assume it for all algorithms (including bogosort), or maybe we have to choose the worst case among a select few algorithms? Is it deterministic, in which case it would suffice to just run the algorithm and count the comparisons, or is it randomistic? So far it seems only in the last, probabilistic, case this has a potential to be NP-hard (though seems more likely coNP-hard).
rus9384
CC BY-SA 4.0
2024-02-09T05:36:51.793Z
I'm very sorry, but I don't understand at all what you are saying. I'm looking at deterministic algorithms, as usual, and I want my algorithm to sort every input under a given number of steps, as usual. For more, you can see this page: https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
domotorp
<np-hardness><sorting><worst-case>
Is sorting NP-complete?
domotorp
# Is sorting NP-complete?

(Asked by: username_0 on 2024-02-05)

SORTING problem.  
Input: A poset which corresponds to a partially sorted list of different numbers.  
Output: Number of pairwise comparisons needed (in the worst case) to get a completely sorted array.  
Is SORTING NP-hard?  
Is it NP-complete to decide whether less than $k$ comparisons are enough to finish?

Surprisingly, I couldn't find anything about this problem.

**Tags:** np-hardness, sorting, worst-case
> **Comments:**
> **username_1**: You probably know this as you have another post on this problem but if you impose zero conditions on the order (i.e. all elements are free to ordered in any way) then your question becomes "can we sort n elements using only k comparisons?" which has been studied without as listed in your other post…  
> **username_1**: Why do you ask for NP? The problem clearly is in PSPACE, but do you have any intuition why it would be in NP?  
> **username_0**: That is a good point, I haven't realized that. It could very well be PSPACE-complete, after all, this is like a 2-player game.  
> **username_2**: Possibly related: https://cstheory.stackexchange.com/q/53874/8237  
> **username_3**: Also an old related question of mine: https://cs.stackexchange.com/questions/60807/is-greedy-minimax-permutation-rejecting-sorting-optimal  
> **username_0**: @Neal I think that the problem you link to is quite different. There we know the values, so it is a full information game, and we want to count the swaps. Here we do not count swaps, but queries.  
> **username_2**: Yes, I agree.  Nonetheless I had some vague hope that one might do a reduction from that problem to yours.  
> **username_4**: Would not the worst case be dependent on an algorithm?  
> **username_0**: @rus9384 Yes, it would.  
> **username_4**: Is the algorithm a part of the input/fixed or should we assume it for all algorithms (including bogosort), or maybe we have to choose the worst case among a select few algorithms? Is it deterministic, in which case it would suffice to just run the algorithm and count the comparisons, or is it randomistic? So far it seems only in the last, probabilistic, case this has a potential to be NP-hard (though seems more likely coNP-hard).  
> **username_0**: I'm very sorry, but I don't understand at all what you are saying. I'm looking at deterministic algorithms, as usual, and I want my algorithm to sort every input under a given number of steps, as usual. For more, you can see this page: https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list  

---

## 1 answers

### Answer by username_5 on 2024-02-10. Score: 3

This is not a full answer, but some partial pieces of information (which you might already be aware of).

---

This is related to the number of linear extensions of the poset. It is known that the worst-case number of comparisons needed to sort a poset $P$ is between $\log\_2 e(P)$ and $\log\_{2}\left(\frac{11}{3}\right)\log\_2 e(P)$ ($\approx 1.874\log\_2 e(P)$) , where $e(P)$ is the number of linear extensions of $P$. The lower bound is easy, the upper bound follows from a relaxation of the 1/3–2/3 conjecture proven in [1].

Counting the number of linear extensions is $\#P$-hard, but there are fully polynomial-time randomized approximation schemes for it, so you can approximate the worst-case number of comparisions needed within a factor of $(1+\epsilon)\log\_{2}\left(\frac{11}{3}\right)$ in randomized polynomial time.

You can also approximate within a factor of $9.82$ in deterministic polynomial time [3, top row of Table 1].

I guess you might be able to find more relevant stuff by searching for "sorting under partial information" or looking at papers which cite or are cited in the ones I mentioned.

[1] *Kahn, Jeff; Saks, Michael*, [**Balancing poset extensions**](https://doi.org/10.1007/BF00565647), Order 1, 113-126 (1984). [ZBL0561.06004](https://zbmath.org/?q=an:0561.06004).

[2] *Brightwell, Graham; Winkler, Peter*, [**Counting linear extensions**](https://doi.org/10.1007/BF00383444), Order 8, No. 3, 225-242 (1991). [ZBL0759.06001](https://zbmath.org/?q=an:0759.06001).

[3] *Cardinal, Jean; Fiorini, Samuel; Joret, Gwenaël; Jungers, Raphaël M.; Munro, J. Ian*, [**Sorting under partial information (without the ellipsoid algorithm).**](https://arxiv.org/abs/0911.0086), Combinatorica 33, No. 6, 655-697 (2013). [ZBL1315.06002](https://zbmath.org/?q=an:1315.06002).

> **Comments:**
> **username_0**: Thanks, but indeed I was aware of these and I don't see why they would help in answering my question.  
> **username_5**: @domotorp I suspected. Still, I thought this was relevant information (it places some kind of upper bound on the optimization problem) and too long for a comment.  

---

