HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is Green's the best 16-input sorting network so far?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
sortingtheinputfargreennetworkbest

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#60242, answer score: 8

Revisions (0)

No revisions yet.