Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

жизнь

Был сегодня в Станфорде на лекции В.И.Арнольда. Арнольд был очень живой и веселый, рассказывал много интересного. В какой-то момент я осознал, что прямо передо мной сидит и слушает Арнольда Дональд Кнут :)

Арнольд рассказывал об определенном подходе к измерению сложности конечных строк (не сложность по Колмогорову). Предположим, у нас есть строка нулей и единиц длиной n. Мы можем представить эту строку в виде функции f из Z_n в {0,1}, где f(i), 0≤i<n, определяет, стоит на i-том месте в строке 0 или 1. Другая возможность визуализации такой строки - она обозначает определенную вершину n-мерного единичного куба.

Вычислим строку разностей соседних битов данной строки, т.е. бит i в новой строке будет разницей битов i+1 и i в старой строке, без переносов между битами и заворачивая n-ный бит обратно в 0. Если, скажем, эта новая строка будет одни нули, это означает, что исходная строка была линейной функцией. Если нет, то вычислим следующую строку, если теперь будут одни нули, то исходная строка была квадратичным многочленом, итд. Вычисление строки разностей является применением определенного оператора A над функциями из Z_n в {0,1}. Последовательное применение A в конце концов приводит к циклу. Выпишем все строки длиной n, и сделаем из них направленный граф, где стрелка из одной строки в другую означает применение A. Как будет выглядеть этот граф?

Это будет лес из нескольких разъединенных между собой графов. Каждый из этих отдельных графов будет состоять из ровно одного цикла, к вершинам которого присоединяются хвосты-деревья. Один из отдельных графов, т.е. один из connected components леса, будет графом многочленов: его цикл состоит из замыкающейся на себя строки 00....0, а дерево, присоединяющееся к этому нулю, содержит все функции-многочлены начиная с линейных, потом квадратичные итд. Другие connected components (если они есть) выглядят по-другому: их циклы длиннее, и к ним присоединяется больше одного дерева. Оказывается, что для данного графа все деревья, которые приводят к вершинам его цикла, изоморфны между собой. Эти деревья все одинаковы по структуре, их можно классифицировать одним параметром глубины. Циклы можно классифицировать одним параметром их размера. Полностью весь лес можно записать в таком виде: 9 O(3)xT(4) + 5 O(2)xT(2) + O(1)*T(15), например, означает 9 изоморфных копий графа, состоящего из цикла из трех вершин, к каждой из которых присодиняется дерево глубины 4, плюс 5 копий графа итд. (цифры неточны, я их выбрал наугад). Выпишем такую запись леса для многих значений n и будет искать и доказывать закономерности между этими коэффициентами. Далее следовало несколько примеров таких закономерностей.

Если мы посмотрим на случайную строку из 0 и 1, то она почти наверняка окажется в графе с самым длинным циклом из всех графов данного леса, притом в дереве этого графа она будет где-то высоко (т.е. далеко от самого цикла). В этом смысле почти все строки "сложные" (к ним нужно много раз применять A, чтобы дойти до цикла, и сам цикл длинный). Поскольку по Колмогорову тоже почти все строки "сложные", выходит, что это определение сложности хорошо коррелирует с определением сложности по Колмогорову, но не по внутренним причинам, а из статистических соображений.

После лекции еще немного (вместе с еще двумя коллегами из Гугла, с которыми туда приехал) поговорили с Кнутом, и много - с Арнольдом, хотя в основном это заключалось в том, что говорил он :), и рассказывал очень много интересного. Я попытался пригласить его прочитать лекцию к нам в Гугль, но он решительно отказался. По-моему, он не очень любит Интернет, поисковые сайты и особенно Википедию.

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 36 comments