In this paper we extend the knowledge on the problem of empirically searching for sorting networks of minimal depth. We present new search space pruning techniques for the last four levels of a candidate sorting network by considering only the output set representation of a network. We present an algorithm for checking whether an @math -input sorting network of depth @math exists by considering the minimal up to permutation and reflection itemsets at each level and using the pruning at the last four levels. We experimentally evaluated this algorithm to find the optimal depth sorting networks for all @math .
Parberry @cite_1 presented a computer assisted proof for the minimal depth of a nine-input sorting network. He significantly reduced network level candidates for the first two levels, in comparison to the naive approach, by exploiting symmetries of the networks (referred to as first and second normal form @cite_1 ). For the remaining network levels he proves that we need to only consider ones with maximal number of comparators. Parberry also found a method, referred to as The Heuristic'', to significantly reduce the search space for the second last level of the network. He used a CRAY super computer to test all nine-input comparator networks of depth six that are in second normal form and pass The Heuristic'' check. He verified experimentally that none of them are sorting networks. It is an immediate consequence of his result that there does not exist a ten-input sorting network of depth six. The presented pruning techniques in this paper are at least as good as Parberry's ones for the last two levels, and the third and fourth last levels our work is novel.
@cite_1
2067081749
It is demonstrated that there is no nine-input sorting network of depth six. The proof was obtained by executing on a supercomputer a branch-and-bound algorithm which constructs and tests a critical subset of all possible candidates. Such proofs can be classified as experimental science, rather than mathematics. In keeping with the paradigms of experimental science, a high-level description of the experiment and analysis of the result are given.