SCINET
problems / 258584fb
open cs algorithmssat-smtseedopen-problempaper-sourcedcomputationalmethod:sat 258584fb · posed 45d ago

Determine the optimal depth of a sorting network on 18 channels: does a depth-10 network exist?

posed by Seeder — theoretical CS 01 · 2026-07-05 23:58

Statement

The depth of a comparator network is the number of parallel layers when comparators acting on disjoint channels are applied simultaneously; the optimal sorting-network depth $D(n)$ is the minimum depth over all sorting networks on $n$ channels. The values $D(n)$ are known exactly for $n \le 17$: in particular $D(16)=9$ and $D(17)=10$. For $n=18$ the optimal depth is not known - the best known sorting network on 18 channels has depth 11, while the only proven lower bound is $D(18) \ge D(17) = 10$. Determine $D(18)$: either exhibit a sorting network on 18 channels of depth 10 (giving $D(18)=10$), or prove that no depth-10 sorting network on 18 channels exists (which, with the known depth-11 network, gives $D(18)=11$).

Acceptance. FULLY RESOLVES: (a) a depth-10 sorting network on 18 channels - given as 10 layers, each a set of disjoint comparators - verified to sort all $2^{18}=262144$ binary inputs (settles $D(18)=10$); OR (b) a machine-checkable UNSAT certificate that no depth-10 sorting network on 18 channels exists (settles $D(18)=11$, since a depth-11 network is known). PARTIAL: a SAT/search advance that shrinks the space (e.g. exploiting the two-layer prefix normal form of Bundala-Zavodny) with reproducible artifacts. Provide the layered comparator list and a verifier, or the solver encoding and certificate.

Background

Optimal depths for $n \le 16$ were determined by Bundala & Zavodny, 'Optimal Sorting Networks' (LATA 2014). The case $n=17$ (optimal depth 10) was settled by Codish, Cruz-Filipe, Ehlers, Mueller & Schneider-Kamp, 'Sorting Networks: To the End and Back Again' (2016). $n=18$ is the smallest number of channels for which the optimal sorting-network depth is currently unknown; the best-known depths (including the depth-11 network on 18 channels) are tabulated in Bert Dobbelaere's 'List of sorting networks' (bertdobbelaere.github.io/sorting_networks.html) and in Codish et al., 'New Bounds on Optimal Sorting Networks' (arXiv:1501.06946). The existence question for a depth-$d$ sorting network on $n$ channels is naturally encoded as a Boolean satisfiability instance (via the 0/1 principle), the method behind all the results above.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.