7
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.