Журнал Компьютерра - Журнал «Компьютерра» №31 от 30 августа 2005 года

Что же это такое - сложность алгоритма (в рамках статьи речь пойдет лишь о временно,й сложности [time complexity] классических детерминированных алгоритмов, а о сложности по объему требуемой памяти, вероятностных алгоритмах, протоколах для бесед вездесущих Боба и Алисы, параллельных и квантовых вычислениях мы, возможно, расскажем в следующих сериях)? Интуитивно это понятие довольно простое. У алгоритма есть вход (input) - описание задачи, которую нужно решить. На ее решение алгоритм тратит какое-то время (то есть количество операций). Сложность - это функция от длины входа, значение которой равно максимальному (по всевозможным входам данной длины) количеству операций, требуемых алгоритму для получения ответа.

Пример. Пусть дана последовательность из нулей и единиц, и нам нужно выяснить, есть ли там хоть одна единица. Алгоритм будет последовательно проверять, нет ли единицы в текущем бите, а затем двигаться дальше, пока вход не кончится. Поскольку единица действительно может быть только одна, для получения точного ответа на этот вопрос в худшем случае придется проверить все n символов входа. В результате получаем сложность порядка cn, где c - количество шагов, потребное для проверки текущего символа и перехода к следующему. Поскольку такого рода константы сильно зависят от конкретной реализации, математического смысла они не имеют, и их обычно прячут за символом O: в данном случае специалист по теории сложности сказал бы, что алгоритм имеет сложность O(n); иными словами, он линейный. Говорят, что алгоритм полиномиальный, если его сложность оценивается сверху некоторым многочленом p(n); алгоритм экспоненциальный, если его сложность имеет порядок 2cn. В реальных, тем более промышленных, задачах редко используются алгоритмы со сложностью больше экспоненты: уже экспоненциальная сложность стала во многих (но не во всех, как мы увидим ниже) случаях синонимом практической неразрешимости и ужасной немасштабируемости. В этой статье мы более никакими теоретико-сложностными концепциями, кроме полиномиального и экспоненциального алгоритма, пользоваться не будем.

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

Мы собирались поговорить о том, насколько теоретические успехи в теории сложности связаны с практикой. В журнальной статье, конечно, невозможно дать обзор всех успехов и неудач теории сложности, так что мы остановимся лишь на трех примерах. Первый из них - биоинформатика - позитивный; в этой области любые теоретические продвижения весьма желательны с практической точки зрения (и продвижения постоянно происходят). Другой пример - линейное программирование - напротив, негативен: здесь один из крупнейших прорывов в теории сложности оказался абсолютно неприменим на практике. Ну а третий пример - решение задачи пропозициональной выполнимости - на мой взгляд, достаточно точно отражает современный баланс между теорией и практикой. Итак, вперед.

Об успехах современной генетики наслышаны многие. Вряд ли сейчас нужно пересказывать истории об овечке Долли, а также - что куда ближе к теме этой статьи - о расшифровке генома человека. Подчеркнем лишь, что расшифровка генома вряд ли могла быть возможной без активного участия теоретической информатики.

Правила, по которым последовательность нуклеотидов гена транслируется в последовательность аминокислот соответствующего протеина (эти правила, собственно, и называются генетическим кодом), были известны еще в 1960-х годах. Каждая тройка нуклеотидов - так называемый кодон - переходит в одну аминокислоту. Нуклеотидов бывает всего четыре, поэтому возможных вариантов кодонов 64; но так как аминокислот около 20, то разные кодоны могут кодировать одну и ту же аминокислоту; есть специальный выделенный кодон, означающий «начало передачи данных», а любой из других трех выделенных кодонов (стоп-кодонов) означает «конец передачи».

Конечный (совсем небольшой) алфавит, дискретные объекты, четкие правила - ситуация идеально укладывается в общую концепцию computer science. Осталось лишь понять, что нужно сделать. Вот типичная задача (так называемая sequence alignment problem): предположим, что даны две последовательности нуклеотидов и набор возможных операций (мутаций) - например, удаление одного нуклеотида или замена одного нуклеотида на другой. Требуется определить минимальную (относительно весов, отражающих вероятности появления тех или иных мутаций) последовательность таких операций, которые первую последовательность переведут во вторую. Иным словами, нужно найти наиболее вероятную цепочку мутаций, которые привели к появлению слона из мухи или человека из обезьяны.

Другая задача, которая составляла основу проекта по реконструкции генома человека, - составление единой последовательности нуклеотидов из данных обрывков (задача возникает потому, что существующие биотехнологии не позволяют выявить структуры длинных последовательностей нуклеотидов - их приходится «разрезать» на кусочки и потом собирать по частям). Нечто вроде сборки паззла, только неизвестно, как сильно перекрываются кусочки и дают ли они в сумме полную картину.

Главная сложность, которая и делает подобные задачи интересными, - это, конечно, их размер[Мы никоим образом не хотим умалить трудности сугубо биологического характера: до середины 1970-х никто и мечтать не мог о том, что такие задачи вообще возникнут, и современное положение дел создано в первую очередь руками биологов. И сейчас биологические проблемы получения и интерпретации данных для комбинаторных задач стоят очень остро, но мы сейчас сконцентрируемся на математических трудностях]. Длина генома человека - более трех миллиардов нуклеотидов; собирать паззлы такого размера могут только компьютеры. А, например, пространство поиска для задачи sequence alignment для двух последовательностей длины 100 содержит порядка 1030 вариантов! Кроме того, задач еще и очень много (конечно, геном у человека один, но ведь есть и другие задачи, и другие организмы): база данных GenBank, содержащая практически всю известную на сей момент генетическую информацию, насчитывает в общей сложности около 50 млрд. нуклеотидов (желающие могут скачать базу с ftp.ncbi.nih.gov/genbank - только будьте готовы к тому, что в ней больше сотни гигабайт).

В результате каждое продвижение в теории сложности алгоритмов для нужд биоинформатики находит практическое применение: ведь зачастую входом алгоритму служит весь GenBank, и сказываются даже минимальные асимптотические улучшения.

Например, одна из связанных с sequence alignment задач - найти минимальное количество операций разворота подпоследовательности (reversals), с помощью которых можно получить данную перестановку из единичной. Поскольку эта задача NP-полна (это означает, что, вероятнее всего, никакого алгоритма быстрее экспоненциального существовать для неё не может), теоретическая борьба шла за создание аппроксимационных алгоритмов, которые бы работали полиномиальное время и давали результат с приемлемой точностью. В 1995 году появился алгоритм, вычисляющий это количество с точностью 2 (т.е. он мог ошибаться в 2 раза). В течение последующих трёх лет этот результат различными исследователями улучшался трижды (!): сначала до 1.75, затем до 1.5, и, наконец, до 1.375.

Характер задач биоинформатики таков, что теоретические оценки, как правило, подтверждаются на практике. Но это не всегда так, и один из важнейших контрпримеров мы рассмотрим в следующем разделе.

Линейное программирование (ЛП) - это задача оптимизации линейной функции при линейных же на нее ограничениях. В наиболее простой переформулировке она сводится к тому, разрешима ли данная система линейных неравенств. Эта кажущаяся абстрактной задача имеет огромное количество применений и возникает в самых разных оптимизационных приложениях. В клиентах у крупнейшего производителя софта для решения задач ЛП - французской компании - ходят такие индустриальные гиганты, как Siemens, IBM, Visa International, France Telecom, United Airlines и многие другие. Говорят, что когда-то советская государственная программа развития Госплана фактически сводилась к тому, чтобы закодировать всю экономику СССР в виде огромной задачи линейного программирования, а потом ее решить и получить оптимальный план[Об этом Л. В. Канторович говорил в своей Нобелевской лекции. Кстати, векторы, лежащие в ограниченном задачей многограннике, в русской терминологии до сих пор называют планами].

Хотя о пользе решения систем линейных неравенств размышлял еще Фурье, впервые о применениях ЛП заговорили во второй четверти XX века. Начавшиеся исследования сразу же привели к успеху: по всей видимости, независимо друг от друга американец Джордж Данциг (George Dantzig) и советский математик Леонид Витальевич Канторович пришли (для разных, но эквивалентных формулировок исходной задачи) фактически к одному и тому же результату. Этот результат называется сейчас симплекс-методом; суть его - в обходе вершин соответствующего задаче многогранника в поиске оптимума. Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач. Важность его столь велика и бесспорна, что после того, как работы Канторовича были опубликованы, его приоритет доказан, а сам математик начал активно пропагандировать применение оптимизационных задач на практике, Л. В. Канторович получил Нобелевскую премию - по экономике, разумеется.