### Resumé

_{n}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 R

_{n}. For each network in R

_{n}, 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.

Originalsprog | Engelsk |
---|---|

Tidsskrift | Journal of Computer and System Sciences |

Vol/bind | 84 |

Sider (fra-til) | 185-204 |

ISSN | 0022-0000 |

DOI | |

Status | Udgivet - 2017 |

### Fingeraftryk

### Citer dette

*Journal of Computer and System Sciences*,

*84*, 185-204. https://doi.org/10.1016/j.jcss.2016.09.004

}

*Journal of Computer and System Sciences*, bind 84, s. 185-204. https://doi.org/10.1016/j.jcss.2016.09.004

**Optimal-depth sorting networks.** / Bundala, Daniel; Codish, Michael; Cruz-Filipe, Luís; Schneider-Kamp, Peter; Závodný, Jakub.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

TY - JOUR

T1 - Optimal-depth sorting networks

AU - Bundala, Daniel

AU - Codish, Michael

AU - Cruz-Filipe, Luís

AU - Schneider-Kamp, Peter

AU - Závodný, Jakub

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

U2 - 10.1016/j.jcss.2016.09.004

DO - 10.1016/j.jcss.2016.09.004

M3 - Journal article

VL - 84

SP - 185

EP - 204

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

ER -