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

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

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