Single-exception sorting networks and the computational complexity of optimal sorting network verification

Asorting 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 optimalsingle-exception sorting networks is demonstrated. These are networks which sort all zero-one inputs except one. More specifically, their depth isD(n-1)+2log(n-1)+2, whereD(n) is the minimum depth of ann-input sorting network. It follows that the verification problem for sorting networks of depth 2D(n)+6logn+O(1) is Co-NP complete. Given the current state of knowledge aboutD(n) for largen, this indicates that the complexity of verification for shallow sorting networks is as great as for deep networks.This research was supported by NSF Grant CCR-8801659.