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

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