2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Колмогоровская сложность. Помогите доказать простую оценку.
Сообщение31.03.2016, 12:35 


16/12/14
472
Пусть $m, n$ - натуральные числа, требуется доказать следующее неравенство:
$\left\lvert KS(m) - KS(n)\right\rvert \leqslant \log\left\lvert m - n\right\rvert  + c$, где
$KS(x)$ - колмогоровская сложность, $c$ - константа, логарифм, естественно, двоичный.

Собственно, что можно сказать прямо сходу про эту ситуацию:

1) $\left\lvert KS(m) - KS(n)\right\rvert \leqslant KS(m) - KS(n)$ (Это обычное неравенство про модуль)
2) $KS(\left\lvert m - n\right\rvert) \leqslant \log \left\lvert m - n\right\rvert + c$ (Длина натурального числа в двоичной записи)
3) Поскольку процесс вычисления модуля от разности двух натуральных чисел можно вычислить с помощью некоторого алгоритма, то тогда можно записать следующую цепочку неравенств:
$KS(\left\lvert m - n\right\rvert) = KS(A(m, n)) \leqslant KS(mn) +c \\
KS(mn) \leqslant KS(m) + \log KS(m) + KS(n) + c$

Дальнейший ход мысли мне не совсем ясен, ничего путного сходу из данных неравенств сконструировать не удается, значит надо обращаться к определнию колгомоговской сложности и пытаться подкрадываться к оценку через различные алгоритмы описания, возможно это сработает.
Прошу указать направление в котором нужно двигаться, потому как в этой теме я абсолютный новичек и потому пока не имею интуиции, подсказывающей верные идеи.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: DariaRychenkova


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group