We consider the construction of minimal multilayered perceptrons for solving combinatorial optimization problems. Though general in nature, the proposed construction method is presented as a case study for the sorting problem. The presentation starts with an O((n!)2) three-layered perceptron based on complete enumeration, that solves the sorting problem of n numbers. This network is then gradually reduced to an O(n2) three-layered perceptron, which can be viewed as a neural implementation of Preparata's parallel enumerative sorting algorithm.
Zwietering, P. J., Aarts, E. H. L., & Wessels, J. (1993). The construction of minimal multilayered perceptrons : a case study for sorting. Neurocomputing, 5(4-5), 197-210. https://doi.org/10.1016/0925-2312(93)90007-P