SINGLE-EXCEPTION SORTING NETWORKS AND THE COMPUTATIONAL-COMPLEXITY OF OPTIMAL SORTING NETWORK VERIFICATION

A sorting network is a combinational circuit for sorting constructed from comparison-swap units. The depth of such a circuit is a measure of its running time. It is known that sorting-network verification is computationally intractable. However, it is reasonable to hypothesize that only the fastest (that is, the shallowest) networks are likely to be fabricated. It is shown that the verification of shallow sorting networks is also computationally intractable. Firstly, a method for constructing asymptotically optimal single-exception sorting networks is demonstrated. These are networks which sort all zero-one inputs except one. More specifically, their depth is D(n-1)+2⌈log(n-1)⌉+2, where D(n) is the minimum depth of an n-input sorting network. It follows that the verification problem for sorting networks of depth 2 D(n)+6⌈log n⌉+O(1) is Co-NP complete. Given the current state of knowledge about D(n) for large n, this indicates that the complexity of verification for shallow sorting networks is as great as for deep networks. © 1990 Springer-Verlag New York Inc.