Editing Sorting network (section)

===Complexity of testing sorting networks===

Unless [[P vs NP|P=NP]], the problem of testing whether a candidate network is a sorting network is likely to remain difficult for networks of large sizes, due to the problem being [[co-NP]]-complete.<ref name=parberry>{{cite conference |last=Parberry|first=Ian|title=On the Computational Complexity of Optimal Sorting Network Verification|journal=Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, the Netherlands |year=1991|pages=252–269}}</ref>