Золотой билет - Страница 28

2. Андрей Николаевич Колмогоров – крупнейший ученый в истории русской науки – предложил в качестве меры сложности алгоритмическую информацию.

3. Ученик Колмогорова Леонид Анатольевич Левин независимо от Кука сформулировал проблему равенства классов P и NP и пришел к понятию NP-полноты. На родине защитить диссертацию он не смог по политическим причинам.

Сергей Всеволодович Яблонский

В Советском Союзе исследования в области теории вычислений проводились в рамках теоретической кибернетики. Активное развитие этой области началось в 1950-х годах, когда электронные вычислительные машины были взяты на вооружение военными. Сергей Яблонский родился в 1924 году в Москве. Вернувшись с фронта после окончания Второй мировой войны, он продолжил изучать математику в Московском государственном университете. В 1953 году Яблонский защитил кандидатскую диссертацию под руководством Петра Сергеевича Новикова, который одним из первых в СССР начал заниматься проблемами вычислимости. Вместе с Алексеем Андреевичем Ляпуновым, также работавшим под руководством Новикова, Яблонский проводил в МГУ семинары по вопросам реализации булевых функций. Яблонский и Ляпунов организовывали и направляли всю исследовательскую деятельность в области теории вычислений.

Проблема выполнимости, упомянутая в четвертой главе, касается логических формул, т. е. формул, в которых основными операциями являются «И», «ИЛИ» и «НЕ». На самом деле любой вычислительный процесс можно представить в виде набора таких операций, или, другими словами, в виде схемы из элементов «И», «ИЛИ» и «НЕ». Одни задачи решаются схемами небольшого размера, для других необходимо огромное число элементов. Возникает понятие схемной сложности, и в начале пятидесятых Яблонский этим понятием заинтересовался.

Основатель теории информации – американский ученый Клод Шеннон – доказал, что некоторые логические функции имеют чрезвычайно высокую схемную сложность. Яблонский решил исследовать сложность построения таких функций. Хоть это и не очевидно, но если P и NP окажутся не равны, отсюда будет следовать, что некоторые легко формулируемые поисковые задачи нельзя решить при помощи маленьких схем.

Из результатов Шеннона вытекало, что сложность логических функций, заданных случайным образом, почти всегда близка к максимальной. Яблонский первым обратил внимание на этот факт и начал заниматься вопросом поиска сложных логических функций без использования случайных величин. Возникала ли при этом необходимость полного перебора всех функций? Ученый показал, что во время построения последовательности функций, имеющих сложную схемную реализацию, обязательно будут строиться и все остальные функции. Отсюда, в частности, следовало, что всякий метод построения некоторой сложной функции можно преобразовать таким образом, чтобы он строил любую другую функцию. Из того факта, что при построении сложных функций строятся также и все остальные, Яблонский сделал вывод о необходимости перебора. В 1959 году вышла его работа «О невозможности элиминации перебора всех функций из P при решении некоторых задач теории схем».

Важность результатов Яблонского сложно переоценить; и все же интерпретировал он их не совсем верно. Ведь если при построении сложной функции можно получить и любую другую, то это еще не означает, что строить все остальные функции необходимо и другим способом сложную функцию никак не найти. На самом деле в работе Яблонского мало что говорилось о вычислительной сложности поиска самых сложных функций. Годом позже ученик Яблонского Юрий Иванович Журавлёв опубликовал статью с не менее впечатляющим названием – «О невозможности построения минимальных дизъюнктивных нормальных форм функций алгебры логики в одном классе алгоритмов», в которой тема вычислительной сложности также не затрагивалась. По сути ни та ни другая работа не касалась вопросов, связанных с проблемой равенства P и NP.

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

Андрей Николаевич Колмогоров

Андрей Колмогоров родился в 1903 году в Тамбове. В 1920 году он поступил в Московский университет, где поначалу интересовался не только математикой, но и пробовал свои силы и в истории, занимаясь изучением налогообложения на Руси в Средние века. Вопрос в его работе ставился такой: назначался ли налог сразу целому селению или же складывался из налогов, назначенных отдельных дворам? Проанализировав старинные налоговые записи, Колмогоров показал: расшифровать эти записи и объяснить правило, по которому они составлялись, будет гораздо проще в предположении, что налог назначался селению. На историческом отделении работу студента оценили очень высоко. Однако в ответ на вопрос, следует ли ему опубликовать полученные результаты, Колмогоров услышал: «У вашей гипотезы есть лишь одно обоснование. А для публикации требуется как минимум два», что в конечном итоге заставило его отвернуться от истории и посвятить себя науке, в которой одного доказательства было вполне достаточно. Колмогоров внес неоценимый вклад в самые разные области математики; это величайший математик XX века и один из крупнейших ученых в истории всей российской и мировой науки.