Неразрешимые задачи и нижние оценки. Лекция Александра Шеня в Яндексе
Понятно, зачем теоретики находят эффективные алгоритмы решения задач какого-то класса, а потом практики их реализуют. Но теоретики стараются также доказать, что для некоторых задач эффективных алгоритмов (и даже вообще никаких алгоритмов) не существует. Что при этом им удаётся и не удаётся, и зачем это может быть нужно? В лекции речь идет о «проблеме остановки» и задачах, к которым она сводится, о знаменитом классе NP, а также о простых нижних оценках.
Лекция был прочитана в Малой Школе анализа данных, которую Яндекс организует для старшеклассников. Автор — Александр Шень. Окончил мехмат МГУ, под руководством Владимира Успенского, ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии». Сейчас является сотрудником Института проблем передачи информации им. А.А. Харкевича РАН и Лаборатории Национального центра научных исследований Франции. Научные интересы: алгоритмы, колмогоровская сложность, логика, теория информации. Почти все книги, которые Александр Ханиевич написал о математике и программированию, находятся в свободном доступе.
Под катом — расшифровка лекции.
Есть стандартная схема, с которой всегда все начинают, — как вообще применяются компьютеры: что есть некоторая проблема в жизни, есть ее математическая формулировка, есть какой-то алгоритм, который решает эту задачу, есть его реализация, ну и после этого его «внедряют». На каждом шаге этой схемы возможны разные препятствия.
Главное препятствие: сама задача, которая ставится, вообще неправильная. В советское время внедряли АСУ (АСУ — автоматизированная система управления). Считалось что социализм — это учет и контроль и надо, чтобы на всех предприятиях стояли компьютеры, которые сообщают в Совет министров, сколько чего произведено, где на складе чего-то не хватает — в общем, полную информацию. Из этого так ничего и не вышло — не только потому, что компьютеры были плохие, но и потому, что задача была выбрана неправильно. Задача может быть совершенно реальной, но ее математическая постановка неправильна. Может выясниться, что математическая задача неразрешима, то есть не существует алгоритма, который ее решает. Или другой вариант: задача может быть разрешима, но неизвестно, как ее решать быстро. И то, с чем мы сталкиваемся каждый день: все разрешимо, и алгоритмы быстрые, но программа неправильная, поэтому ничего не действует. И наконец, программа может быть правильная, но есть проблемы с ее реализацией.
Нас интересуют неразрешимые проблемы и сложные алгоритмы. Смысл, который нас интересует: проблема алгоритмически неразрешима и это массовая проблема. Например, есть 10-я проблема Гильберта: про многочлен с целыми коэффициентами (и несколькими переменными) надо узнать, есть ли у него решение. И это алгоритмически сделать нельзя, такого алгоритма в принципе нет. Другой пример задачи, которая в принципе разрешима, — любое целое число можно разложить на множители просто перебором, но нет быстрого алгоритма.
Первая стандартная проблема, с которой начинаются все доказательства неразрешимости, — это проблема остановки. Проблема состоит в том, что надо выяснить по данной программе, остановится она или не остановится. Теория алгоритмов началась с того момента, когда люди доказали, что эта проблема неразрешима. В принципе, чтобы доказывать, что что-то неразрешимо, нужно сформулировать точно, что значит алгоритм, потому что алгоритм Евклида можно было рассматривать, не определяя общего понятия алгоритма. Это было все придумано еще до того, как появились первые процессоры. Была придумана машина Тьюринга, языки программирования. После того как такой язык программирования сформулирован, можно спрашивать, что по программе нужно определить, остановится она или не остановится. Программа, которую мы хотели бы найти, но которой нет, когда ей дают некоторую программу А, должна сказать «да» или «нет» в зависимости от того, остановится А или не остановится. Есть разные варианты этой остановки, например, можно рассматривать программы на разных языках программирования, можно рассматривать программы со входом или без входа. Все эти варианты при разных языках программирования эквивалентны. Например, фирма распространяет программу, позволяющую по любой программе для Macintosh заранее проанализировать ее и сказать, остановится она или не остановится. Как мы можем это использовать, чтобы определить, остановится ли Linux-программа? Более простой технический способ — написать на Macintosh интерпретатор процессора, на котором написана Linux-система, соответственно запустить там эту Linux-систему, и все это вместе станет некоторой программой для системы Macintosh, и она остановится только в том случае, когда остановится та программа. Возможность трансляции показывает, что язык программирования тут несущественная подробность, а важно лишь, умеем ли мы определять, остановится или не остановится программа для какой-то модели.
Почему так важно знать, останавливается программа или не останавливается? Причина в том, что к этому сводится очень много разных задач. Допустим, мы научились узнавать, останавливается программа или нет, тогда мы сразу можем ответить на много разных вопросов, например, можем определить, верна ли теорема Ферма. Надо написать программу, которая ищет контрпример, и спросить, остановится эта программа или не остановится. Это можно сделать про очень многие математические гипотезы.
Есть еще совершенно посторонний ликбез, что множество всех двоичных дробей несчетно, что нельзя все двоичные дроби расположить в последовательности. Если мы напишем первую дробь, вторую, третью и т. д., то всегда есть дробь, которая пропущена. Мы можем построить дробь, которая пропущена, следующим образом. От первой дроби она будет отличаться в первом знаке, от второй дроби — во втором знаке и т. д. Не обязательно брать подряд, можно просто для каждой дроби взять какой-то знак и сделать, чтобы она отличалась в этом знаке. Если мы напишем эти дроби, то всегда можем найти дробь, которой нет в этом списке. Научно это называется «диагональный аргумент Кантора».
Из этого мы легко получим вариант, почему неразрешима проблема остановки. Рассмотрим не все дроби, а только вычислимые дроби. Двоичная дробь называется вычислимой, если есть алгоритм, который выписывает ее, или есть алгоритм, который по номеру позиции говорит, что там стоит. Все известные числа — «пи», «е» — вычислимы, потому что есть соответствующие ряды. Конечно, не все дроби вычислимы, потому что вычислимых дробей только счетное число, и можно сделать такую вещь: напишем все возможные программы, вычисляющие эти дроби. Программы — это конечные объекты, какие-то последовательности битов их можно записать в порядке возрастания. Напишем все программы, которые вычисляют эти десятичные дроби. Как тогда построить невычислимую дробь? Нужно просто применить диагональную конструкцию к программам, вычисляющим все дроби. Получилось противоречие: вроде бы эта самая дробь, которая не вычислима, с другой стороны, все-таки вычислима. У нас имеется список этих программ, мы берем программу номер I они пронумерованы в обычном порядке, смотрим, что эта программа дает на этом месте, и пишем в нашу дробь не то, что нам давала программа на этом месте. Мы получаем вычислимую двоичную дробь, которая не входит в список всех вычислимых двоичных дробей, получаем противоречие. Проблема здесь в следующем: программы есть не только, которые всюду останавливаются. Какая-то программа на некоторых входах может вообще никаких битов не давать — ни нуля, ни единицы. И мы заранее этого не знаем, поэтому, когда я говорю, что мы выпишем здесь все программы для бесконечных двоичных вычислимых дробей, — это жульничество. И оно состоит в том, что мы можем выписать все программы, но тогда некоторые из них в некоторых местах ничего давать не будут. А выделить из них те программы, которые всюду что-то дают, мы не можем, и в этом причина противоречия.
Почему проблема остановки неразрешима? Представим, что она была бы разрешима, тогда мы могли бы наше рассуждение исправить. Мы бы составили список из всех программ независимо от того, останавливаются они на каких-то входах или не останавливаются. Дальше мы бы написали новую программу, указав, что она на этом месте хочет отличиться от этой программы, имея в виду, что есть такая опасность. I-тая программа на I-том месте не определена, мы действуем аккуратно. Сначала спрашиваем у проблемы остановки: остановится ли I-тая программа на I-том месте. И, если она говорит, что остановится, тогда мы смело ее запускаем, дожидаемся этого ответа и пишем не тот бит. А если говорит, что не остановится, то тогда мы пишем, например, ноль, потому что мы знаем что эта программа не остановится и поэтому отличиться от нее легко. Можно написать любую цифру, и это все равно будет не то же самое, что дает наша программа. Тем самым мы получили некоторую программу, которая вычисляет последовательность, и этой последовательности здесь нет ни в полных строках, ни в строках с пропусками. Потому что если бы взяли любую строку, то в итой позиции есть отличие. Это неразрешимая проблема остановки.
Как из этого можно получить неразрешимость для каких-то конкретных задач? Это игра, которую придумал Конвей, и она называется FRACTRAN. Игра состоит в следующем. Имеется некоторый список дробей рациональных чисел — конечный список. И имеется некоторое целое число — это такое игровое поле. Вы пытаетесь это число умножить на какую-нибудь из этих дробей, чтобы осталось целое число. Все сходится, если в какой-то момент уже таких чисел нет, и мы заканчиваем работу, видим, что ни на что уже умножить нельзя. Может не сходиться — это означает, что мы все время так делаем и это ничем не кончается. Теорема Конвея — нет алгоритма который по начальной позиции определяет, закончится ли игра Конвея. Эта задача является алгоритмически неразрешимой.
Сейчас попробуем это доказать. Рассмотрим простой язык программирования. Простой язык имеет некоторое количество переменных. Изначально они все равны нулю, вернее, в программе переменных может быть сколько угодно, но программа конечная, поэтому она включает в себя только конечное число. Переменные — это все натуральные числа. У нас есть две команды: первая команда — это увеличить счетчик на единицу, вторая команда — уменьшить какую-то переменную на единицу, но тут ее нельзя уменьшить, потому что она уже равна нулю. Тогда в этой машине возникает прерывание, и в этом случае мы уменьшаем переменную. И, если это невозможно сделать, то нужно переходить к другой строке программы. На этом языке можно запрограммировать любую программу. Как, например, сделать безусловный переход? Нужно завести некоторую переменную, которую мы никогда не увеличиваем, а если мы хотим сделать безусловный переход, мы можем сделать попытку уменьшения этой переменной, и тогда мы сделаем этот переход. Если у нас в программе конечное число переменных, то как же реализовывать массивы? Мы должны закодировать массив в одном числе. Стандартный математический способ: нужно взять число 2 в степени х1 умножить на 3 в степени х2 умножить на Pn в степени хn. Всякое простое число разлагается на простые множители, поэтому можем закодировать наши любые числа степенями этих самых чисел.
Мы сейчас докажем эту теорему, сведя язык программирования к игре Конвея. Наша ближайшая цель — это «сведение». Задача об остановке программы сводится к задаче об остановке игры, т.е. у нас дана некоторая программа, а мы по этой программе построим игру, которая останавливается только тогда, когда останавливается программа. Дана какая-то программа, и в ней имеются какие-то строки, сколько-то есть переменных и строк. Наша задача состоит в том, чтобы построить некоторую игру, которая бы моделировала эту программу т.е. действие в игре конвея должны соответствовать в точности исполнению этой программы. Для примера, переменных 26. Тогда мы будем кодировать их степенями первых двадцатишести простых чисел. Т.е. число, которое в игре Конвея будет на самом деле в себе содержать значение всех переменных. Еще игра должна помнить, какая строка программы — текущая. Какая строка текущая кодируется так: все строки программы занумеруем еще большими простыми числами. Содержимое всех переменных и текущая строка программы кодируется целым числом. Игра моделирует поведение программы в каждый момент игры. Мы должны возвести первые 26 простых чисел в степени, которые в значении переменных, и потом это еще умножить на простое число, которое является меткой текущей строки, — это позволит легко имитировать наши две команды. Что нам нужно сделать, если в строке с номером каким-то Q у нас какую-то переменную C нужно увеличить на единицу? Какие дроби в игре Конвея мы должны для этого предусмотреть? C у нас кодируется как степень числа пять. Мы должны в игре Конвея предусмотреть такую вещь, что если у нас текущая строка это Q, то надо в нашем числе показатель степени при пятерке увеличить на единицу и перейти к следующей строке, которая имеет номер R.
Очевидно, в числители будет пять, потому что прибавление единицы к C соответствует умножению на пять. В знаменателе должно быть нечто, что дало бы этой дроби сработать, когда наша текущая строка Q. Значит, нужно в знаменателе написать Q. Тогда применение этой дроби возможно будет только в том случае, когда наше текущее число содержит Q. Соответственно, надо это умножить на R. На самом деле, в любой последовательности Конвея последовательности дробей пишем: вот дробь. И она срабатывает, когда надо, в остальных дробях будут другие знаменатели, поэтому если текущая строка у нас Q, то может сработать только эта дробь, и получается то, что нужно, а новая строка будет R. Если у нас имеется такая программа, то можно написать последовательность дробей и дальше. Человек, играющий в эту игру, будет, на самом деле, выполнять эту программу. Отсюда станет ясно, что определить, останавливается ли игра, если бы мы это умели, то могли бы также определять, останавливается ли программа в этом языке. До этого мы объясняли, что в этот язык в принципе можно транслировать программу любого другого языка с помощью вот этих приемов. Любую программу мы можем преобразовать в эту конвеевскую игру, и, если бы кто-то мог сказать, остановится эта игра или не остановится, то это можно было бы использовать, чтобы определить остановится данная программа или нет. Раз мы доказали, что остановка программы — неразрешимые сведения, если А сводится к Б и Б разрешимо, то А разрешимо. Значит, если А сводится к Б, и Б неразрешимо, то это ничего не значит, потому что простая задача может сводиться к сложной. Но если мы свели сложную задачу к какой-то, то эта, значит, тоже сложная. Вопрос об остановке игры Конвея неразрешим.
Есть такое понятие, как задача разрешима, но практически никто не знает, как это быстро сделать, например разложение на множители. Можно перепробовать все варианты, но если у вас есть число из тысячи цифр, то вы никогда их не перепробуете, и даже самые быстрые компьютеры не помогут. Есть некоторый класс задач которые называются NP — полные задачи. Это аналог проблемы остановки, но в реальном мире, где нас интересует выполнимость за какое-то реальное время. Не доказано, можно ли их решить быстро. Они все одинаково сложные, если бы одну можно было бы решить быстро, то и все можно было бы решить быстро. Это доказывается с помощью приема сведения одной задачи к другой. Мы ищем объект с каким-то свойством, при этом само свойство — объект небольшой, а свойство — простое, и единственная проблема в том, что объектов много — это называется переборная задача. Если вы что-то пытаетесь запрограммировать, и видно, что возникает NP-полная задача, это означает, что надо что-то делать, надо искать другую математическую модель или вводить дополнительные ограничения, или как-то вообще модифицировать постановку.
