Колмогоровская сложность классов общерекурсивных функций с ограниченной ёмкостью

Доказано двойное неравенство VCD(S) ≤ Kl(S)< VCD(S)log l, где VCD(S) - размерность Вапника-Червоненкеса некоторого семейства общерекурсивных функций, Kl(S) - колмогоровская сложность этого семейства функций S,l - длина выборки. Предложен новый pVCD подход для оценивания VCD на основании приведенного выше двойного неравенства.