# Is sorting NP-complete?

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?

• 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… Feb 5 at 10:07
• Why do you ask for NP? The problem clearly is in PSPACE, but do you have any intuition why it would be in NP? Feb 5 at 10:10
• 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. Feb 5 at 10:49
• Possibly related: cstheory.stackexchange.com/q/53874/8237 Feb 5 at 21:30
• Also an old related question of mine: cs.stackexchange.com/questions/60807/…
– orlp
Feb 5 at 22:08

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, Order 1, 113-126 (1984). ZBL0561.06004.

[2] Brightwell, Graham; Winkler, Peter, Counting linear extensions, Order 8, No. 3, 225-242 (1991). ZBL0759.06001.

[3] Cardinal, Jean; Fiorini, Samuel; Joret, Gwenaël; Jungers, Raphaël M.; Munro, J. Ian, Sorting under partial information (without the ellipsoid algorithm)., Combinatorica 33, No. 6, 655-697 (2013). ZBL1315.06002.

• Thanks, but indeed I was aware of these and I don't see why they would help in answering my question. Feb 10 at 16:01
• @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. Feb 10 at 16:16