ON 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 reasonable to hypothesize that only the fastest (that is, the shallowest) networks are likely to be fabricated. It is shown that the problem of verifying that a given sorting network actually sorts is Co-NP complete even for sorting networks of depth only 4[log n] + O(1) greater than optimal. This is shallower than previous depth bounds by a factor of two.