Optimal sorting networks on three to six channels

Use of Axeyum

Axeyum represented candidate networks and lower-bound obligations as finite search problems and recorded certificates for the resulting sizes.

Components

Axeyum SAT SolverAxeyum Library

Recorded result

The recorded optimum sizes are 3, 5, 9, and 12 comparators for three through six channels.

Supporting artifacts

Artifact pages contain the formal statement, proof route, evidence, provenance, and direct dependency graph recorded in the ledger.

• The optimal sorting network on 3 channels has exactly 3 comparators smt-clausal · F:sorting-network-optimal-size-n3
• The optimal sorting network on 4 channels has exactly 5 comparators smt-clausal · F:sorting-network-optimal-size-n4
• The optimal sorting network on 5 channels has exactly 9 comparators smt-clausal · F:sorting-network-optimal-size-n5
• The optimal sorting network on 6 channels has exactly 12 comparators smt-clausal · F:sorting-network-optimal-size-n6