A complete set of filters @math for the optimal-depth @math -input sorting network problem is such that if there exists an @math -input sorting network of depth @math then there exists one of the form @math for some @math . Previous work on the topic presents a method for finding complete set of filters @math and @math that consists only of networks of depths one and two respectively, whose outputs are minimal and representative up to permutation and reflection. We present a novel practical approach for finding a complete set of filters @math containing only networks of depth three whose outputs are minimal and representative up to permutation and reflection. In previous work, we have developed a highly efficient algorithm for finding extremal sets ( i.e. outputs of comparator networks; itemsets; ) up to permutation. In this paper we present a modification to this algorithm that identifies the representative itemsets up to permutation and reflection. Hence, the here presented practical approach is the successful combination of known theory and practice that we apply to the domain of sorting networks. For all @math , we empirically compute the complete set of filters @math of the representative minimal up to permutation and reflection @math -input networks of depth three.
--- we took an existing algorithm for finding minimal itemsets up to permutation which a dataset (a collection of itemsets). We present a modification which is linear (in terms of the number of itemsets) in time and space to find the ones which are minimal up to permutation and reflection. --- this is a direct improvement of Bundala's technique of not considering all of the @math inputs to determine that no @math -input sorting network of depth @math exists. We take one step further to find the minimal up to permutation and reflection itemsets after applying the input set reduction (described in Experiment 3 @cite_6 ). --- we experimentally evaluated the modified algorithm to find the three layered @math -input comparator networks whose outputs (itemsets) are minimal up to permutation and reflection. The set @math is generated by applying all network levels to @math and then finding the minimal up to permutation and reflection ones, whereas @math is derived by applying all levels to all itemsets in the set @math and then reducing.
@cite_6
1726079515
We prove depth optimality of sorting networks from "The Art of Computer Programming".Sorting networks posses symmetry that can be used to generate a few representatives.These representatives can be efficiently encoded using regular expressions.We construct SAT formulas whose unsatisfiability is sufficient to show optimality.Resulting algorithm is orders of magnitude faster than prior work on small instances. 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 R 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.