ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 5, 52, 55 Makarenko, Alexander, National Technical University (KPI), Kiev, Ukraine The Complexity Measure of individual geometrical and algebraical Objects Often it is necessary to know the complexity measure of individual objects such as graphs combinatorial objects, geometrical figures and functions. There are few strict works for nonprobabilistic objects (A. Kolmogorov, V. Rashevsky, G. Jumaire, J. Yomdin, V. Goppa). Implicitly the dissymmetry of object is the complexity measure in many problems. Results presented in report give strict measure of symmetry in object. The idea is to count the complexity of word in some alphabet. As the measure of complexity it is proposed to take the power of object orbit under the selected group of automorphysms. The description of geometrical object is received by discretization. There are theorems on the complexity measure for Morse function. It is discussed the applications to dynamical systems and information theory.