[Solved]: Is Green's the best 16-input sorting network so far?

Problem Detail: 

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?

Asked By : Christian

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60242