|
|
Колмогоровский семинар по сложности вычислений и сложности определений
17 декабря 2012 г. 16:45–18:30, г. Москва, Главное здание МГУ, ауд. 16-04
|
 |
|
 |
|
|
|
Вычислимые короткие списки, содержащие короткие описания
Н. К. Верещагин |
| Количество просмотров: |
| Эта страница: | 157 |
|
Аннотация:
По данному слову x можно найти список из $O(|x|^2)$ слов, одно из которых является описанием для x длины не более чем на константу превышающей колмогоровскую сложность x. Этот результат использует
двудольные графы, допускающие он-лайн паросочетания мощности примерно равной размеру правой доли, построенных Шенем, Ромащенко и Мусатовым.
(По совместной работе с Баувенсом, Махлиным и Зимандом.)
|
|
Обратная связь: