Abstract: An analogue of a neural network, the number of layers and the number of cells in which may be changed during its retraining is suggested in the paper. The main instrument for constructing such a network is extraction of maximal common properties of pairs of objects in the training set and of that ones used for retraining. The degree of coincidence of a recognized object with the one presented in the training set may be calculated using their maximal common properties. Computational complexities of such a network construction, recognition process and the network retraining are proved. A brief description of a similar network proposed by the author earlier for complex structured objects described using predicate calculus is presented. The analysis of comparison of computational complexity of a complex structured object recognition with various methods of their description is given.