5
$\begingroup$

Every paper says that Green's construction is the best 16-input sorting network as for now.

But why does Wikipedia says: "Size, lower bound: 53"?

I thought "lower bound" meant:"If there exists at least an algorithm that can...". Am I wrong?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
8
$\begingroup$

No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be a smaller one than that.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ It doesn't even mean that there is a 53-gate network. $\endgroup$
    – Raphael ♦
    Jul 2, 2016 at 16:11
6
$\begingroup$

The lower bound for an problem states that "no algorithm can do better than this". In your case, it means that no sorting network for 16 inputs can have fewer than 53 gates.

Sometimes there can be confusion between the reader and writer regarding whether a lower bound is tight or not. A tight lower bound states, "no algorithm can do better than this, and this number is achievable in practice".

A tight lower bound can come from a non-constructive proof or from an actual example that can be applied in practice.

Here is an example from comparison-based sorting algorithms. By combinatorics, the lower bound is $\Omega(n \log n)$ operations to perform sorting. But we also have algorithms like heap sort that take $O(n \log n)$ running time. Therefore in this case, the lower bound is a tight one.

But a different example is the number of moves to solve a standard Rubik's cube. The simple lower bound started at 18, and it took years of research and computation to raise this number to the tight lower bound of 20.

Improve this answer
$\endgroup$
1
  • $\begingroup$ And the diameter of the graph representing $n \times n \times n$ Rubik's cube configurations is $\Theta(n^2/\log n)$ (by Demaine, I believe, who proved upper and lower bounds). $\endgroup$
    – Ryan Dougherty
    Jul 3, 2016 at 5:57
-2
$\begingroup$

there are relatively new results in this area using SAT solvers and some new theory. optimal networks up to n=16 are now known/ constructed. this paper explains the techniques and following is a link given in the paper to optimal sorting network constructions up to n=16. (the paper does not mention Greens construction in particular but it does reference Knuth and maybe that is enough to correlate precisely if Knuth refers to Greens construction.)

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ This paper is about optimal depth, not number of comparators. $\endgroup$
    – Yuval Filmus
    Jul 5, 2016 at 16:43
  • $\begingroup$ :( ok, think the results might resolve the question if translated somehow but agree on 2nd look they are not exactly in the form requested and extracting minimal networks from their formulation may be tricky, but think it is likely the nearest/ most recent published research in the area/ on the nearby question(s) $\endgroup$
    – vzn
    Jul 6, 2016 at 15:47

Your Answer

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

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