Колмогоровская сложность и VC размерность семейств рекурсивных функций

Авторы: 
Журнал: 
Страница: 
32
УДК: 
519.7

Изучается связь между комбинаторной размерностью ($VCD$) Вапника-Червоненкиса и колмогоровской сложностью семейств частично рекурсивных функций. Для произвольного семейства частично рекурсивных функций $\mathfrak{F}$ дано определение колмогоровской сложности $KC(\mathfrak{F})$. Доказано неравенство $VCD(\mathfrak{F})\leq KC(\mathfrak{F})$, на основе которого обоснован $pVCD$ метод получения оценок размерности Вапника-Червоненкиса для произвольных семейств частично рекурсивных функций. Приведены примеры оценивания при помощи $pVCD$ метода.

Ключевые слова: VC размерность, колмогоровская сложность, рекурсивные функции.