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 сообщение ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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