Abstract:
There are two ways of description of a geometrical object $O$: the object as an image of a mapping and the object as a preimage. Each of the ways has its advantages and disadvantages, and together they give the full picture. To compare the complexity of these descriptions, we can use the approach of Kolmogorov: i.e., after the specification of the system of the basic operations the complexity of the description is the minimal lengths of the defining text. Thus, we obtain the two Kolmogorov complexities: in the first case it is $K^{+}(O)$, and in the second case it is $K^{-}(O)$. Let $Cl^n$ be the class of functions of two variables, such that they can be represented by a superposition of depth not greater than $n$ of analytic functions of one variable and addition, and $K^{+}(Cl^n)$ and $K^{-}(Cl^n)$ be the corresponding Kolmogorov complexities. There are arguments that for $n \geq 2$ the value $K^{-}(Cl^n)$ is very big and the problem of description of $Cl^n$ as a preimage (by defining equations) even for $n =2$ can not be realized computationally. Using this observation, we propose a scheme of coding-decoding of signals, and also we give arguments that the proposed coding scheme can not be decoded with the help of a quantum computer.
