Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951263 | Journal of Computer and System Sciences | 2017 | 20 Pages |
Abstract
We solve a 40-year-old open problem on depth optimality of sorting networks. In 1973, Donald E. Knuth detailed sorting networks of the smallest depth known for nâ¤16 inputs, quoting optimality for nâ¤8 (Volume 3 of “The Art of Computer Programming”). In 1989, Parberry proved optimality of networks with 9â¤nâ¤10 inputs. We present a general technique for obtaining such results, proving optimality of the remaining open cases of 11â¤nâ¤16 inputs. Exploiting symmetry, we construct a small set Rn of two-layer networks such that: if there is a depth-k sorting network on n inputs, then there is one whose first layers are in Rn. For each network in Rn, we construct a propositional formula whose satisfiability is necessary for the existence of a depth-k sorting network. Using an off-the-shelf SAT solver we prove optimality of the sorting networks listed by Knuth. For nâ¤10 inputs, our algorithm is orders of magnitude faster than prior ones.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Bundala, Michael Codish, LuÃs Cruz-Filipe, Peter Schneider-Kamp, Jakub Závodný,