THE MINIMAL NUMBER OF LAYERS OF A PERCEPTRON THAT SORTS

In this paper we consider the problem of determining the minimal numbe r of layers required by a multilayered perceptron for solving the prob lem of sorting a set of real-valued numbers. We discuss two formulatio ns of the sorting problem; ABSSORT, which can be considered as the sta ndard form of the sorting problem, and for which, given an array of nu mbers, a new array with the original numbers in ascending order is req uested, and RELSORT, for which, given an array of numbers, one wants f irst to find the smallest number, and then for each number-except the large-stone wants to find the number that comes next in size. We show that, if one uses classical multilayered perceptrons with the hard-lim iting response function, the minimal numbers of layers needed are 3 an d 2 for solving ABSSORT and RELSORT, respectively. (C) 1994 Academic P ress, Inc.