Vi löser ett 40-årigt öppet problem på djupet av sorteringsnätverk. År 1973, Donald E. Knuth detaljerad, i volym 3 av "The Art of Computer Programming", sortering nätverk av den minsta djup känd vid tidpunkten för n ≤ 16 ingångar, citerar optimalitet för n ≤ 8. År 1989 visade Parberry att nätverken var optimala med 9 ≤ n ≤ 10 ingångar. I denna artikel presenterar vi en allmän teknik för att uppnå sådana optimala resultat, och använder den för att bevisa optimaliteten av de återstående öppna fall av 11 ≤ n ≤ 16 ingångar. Vi visar hur man utnyttjar symmetri för att konstruera en liten uppsättning tvålagersnätverk på n-ingångar så att om det finns ett sorteringsnätverk på n-ingångar på ett givet djup, så finns det ett vars första lager finns i denna uppsättning. För varje nätverk i den resulterande uppsättningen konstruerar vi en propositionell formel vars tillfredsställelse är nödvändig för existensen av ett sorteringsnätverk av ett givet djup. Med hjälp av en off-the-shelf SAT-lösare visar vi att sorteringsnätverken som listas av Knuth är optimala. För n ≤ 10 ingångar är vår algoritm order av magnitud snabbare än de tidigare.
Bundala REF presenterade ett datorstödd bevis för optimala djup av nätverk med elva till sexton (inkluderande) ingångar.
Optimal-Depth Sorting Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}