Speaker
Георгий Захаров
(Московский Физико-Технический Институт)
Description
Задачи сравнения рандомизированной и детерменированной Колмогоровских сложностей сводятся к игре Мартина. Если для некоторой константы $c$ в $(\frac{1}{n}, cn^{\alpha})-$игре выигрывают кошки, то верно $I(S) \leq \alpha H(S) + O(log(H(S)))$ Если же выигрывают муравьи, то верно $I(S) \geq \alpha H(S) - O(log(I(S))$. В этой работе доказано выполнение инварианта для муравьев-родителей котов $|\textit{cover}(S)| \geq f(\mu(S))$ для некоторой функции $f$. Это позволяет доказать победу котов в $(\frac{1}{n}, n^{n})$-игре в общем случае, а также победу котов в $(\frac{1}{n}, n^{2})$-игре для достаточно хорошего класса игр.
Primary authors
Александр Шеховцов
(Московский Физико-Технический Институт)
Георгий Захаров
(Московский Физико-Технический Институт)
Даниил Мусатов
(Московский Физико-Технический Институт)
