Книга: Золотой билет

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

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

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

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

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

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

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

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

Оглавление книги