The minimal number of layers of a perceptron that sorts

In this paper we consider the problem of determining the minimal number of layers required by a multi-layered perceptron for solving the sorting problem. We discuss two formulations of the sorting problem; ABSSORT, which can be considered as the standard form of the sorting problem, and where, given an array of numbers, a new array with the original numbers in non-decreasing order is requested, and RELSORT, where, given an array of numbers, one wants to find the smallest number and for each number -except the largest- one wants to find the next largest number. We show that, if one uses classical multi-layered perceptrons with the hard-limiting response function, the minimal number of layers needed is 3 and 2 for solving ABSSORT and RELSORT, respectively. Keywords: multi-layered perceptrons, minimal number of layers, neural networks, sorting.