Окончание, см. начало

Мы уже знаем, что достаточно решить любую из NP-полных задач. Почему-то ученым полюбилась задача о максимальной клике графа.

Граф можно представлять как множество точек - вершин на плоскости, соединенных линиями - ребрами. Нечто вроде карты дорог и городов. Кликой называется часть вершин графа, каждая пара из которых соединена ребром. Максимальной является клика с наибольшим количеством вершин. Попросту говоря, нужно найти на карте самую большую группу городов, каждый из которых напрямую соединен дорогой с другими городами этой группы. Поиск максимальной клики в графе труден, потому что количество всевозможных подграфов в графе из n вершин очень велико (2ⁿ ), и практически только прямой проверкой их всех можно отыскать максимальную клику.

Для задачи о максимальной клике в 1997 году в Принстоне был реализован предложенный в 1994 году алгоритм для экзотического молекулярного «ДНК-компьютера». В нем используют живую бактерию и вирус для вживления ДНК. Подробнее об этом можно прочесть в журнале New Scientist. Есть ряд других попыток, базирующихся на скрытом параллелизме генетических алгоритмов.

Недавно группа ученых из Гарварда под руководством профессора Джорджа Уайтсайдза (George Whitesides) предложила более «реалистичное» устройство. Жидкий компьютер Уайтсайдза способен быстро решить задачу о максимальной клике для любого графа с n вершинами. Опытный образец для графа с шестью вершинами представляет собой пластиковый чип размером с почтовую марку.

Чип состоит из n(n-1)/2 слоев пластика, которые соответствуют ребрам полного графа с n вершинами. В слой сверху вливается порция жидкости с суспензией флуоресцирующих частиц, если соответствующее ребро имеется в анализируемом графе. Затем жидкость течет по капиллярам в слое и вытекает в пронизывающие все слои вертикальные колодцы, каждый из которых соответствует некоторому подграфу графа. Капилляры в слое соединены с колодцем, если ребро слоя принадлежит подграфу колодца. Эту конструкцию удается изготовить без самопересечений капилляров. Под нижним слоем находится фильтр, задерживающий флуоресцирующие частицы, и дополнительный дренажный слой пластика.

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

Авторы утверждают, что за счет параллелизма фотолитографии эту конструкцию можно изготовить быстро - за степенное время, несмотря на то, что число колодцев растет экспоненциально.

Был создан экспериментальный чип с шестнадцатью слоями для графа из шести вершин. Авторы считают, что по новой технологии сегодня можно изготовить чип для графа из 40 вершин. Обычный компьютер решает задачу о клике в таком графе за 20 минут. Поэтому водяной компьютер Уайтсайдза не может конкурировать с обычным.

Нетрудно сообразить, что компьютер Уайтсайдза, да и любые его аналоги, совсем не имеют будущего. Дело в том, что хотя он и позволяет быстро решить задачу, площадь чипа, содержащего 2n колодцев для каждого подграфа, экспоненциально растет при увеличении числа вершин. И если для графа из 40 вершин при каналах толщиной 200 нанометров нужен чип 30х30 сантиметров, то для графа с 93 вершинами потребуется чип с площадью большей, чем у планеты Земля. Есть проблемы и с самой водяной технологией. Капилляры и колодцы в пластике должны быть изготовлены очень точно - с одинаковой толщиной и длиной. Иначе результат жидких вычислений будет ошибочным. Причем длина каналов, а значит и требования к точности их изготовления, да и время течения жидкости растут экспоненциально.

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

Науки бывают естественные и неестественные. К последним можно отнести математику и ее ветвь - теорию алгоритмов, потому что критерий истины в ней не опыт, а формальная логика.

Поэтому каждый физик-теоретик знает, что если в процессе работы неожиданно возникли различные расходимости, полюса, особенности, неподъемные алгоритмы и прочие математические неприятности, то это может означать одно из двух. Либо пойман новый физический эффект, либо его на самом деле нет, а это просто бессодержательные "трудности языка" и следует либо попробовать иной математический метод, либо чуть иначе поставить задачу.

С другой стороны, гораздо реже, но случается, что математики и физики (каждые из своих собственных соображений) приходят, и иногда почти одновременно, к одному и тому же открытию. За логическими неувязками, «лишними» решениями и не решаемыми задачами могут стоять еще не открытые законы природы. Известный пример - древнегреческая аксиома о параллельных прямых. Надо сказать, что в физике, а особенно в квантовой механике, и сегодня очень много логических дыр. Не подойдет ли к одной из них проблема перебора?

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

В качестве примера возьмем задачу линейного программирования. В ней нужно найти x, дающий минимум произведения ax при ограничениях Bx≥с, где a,с и x - векторы размерности n, а B - матрица. К задаче линейного программирования сводятся многие практические проблемы - от планирования экономики страны до оптимальной раскройки ткани. Для нее весьма эффективен «симплекс-метод», который, как правило, быстро находит точное решение. Но на специально подобранных примерах симплекс-метод считает экспоненциально долго. А значит, нет никаких гарантий, что ваша конкретная задача будет решена за обозримое время.

Так вот, если считать исходные данные а, В и с наборами рациональных чисел, и искать решение такого же вида, это гарантированно можно сделать за степенное число шагов - с помощью так называемого алгоритма Хачияна. Если же потребовать, что вектор решения x должен состоять из целых чисел, то задача становится NP-полной.

Если мы попытаемся придумать классическое аналоговое устройство для решения задач перебора, то, очевидно, встанет проблема, как впихнуть большое число вариантов решения в ограниченный объем. Даже если один вариант потребует объема только одного атома, то и в кубический метр не поместятся задачи коммивояжера или задача о клике даже для сотни городов. Те же проблемы характерны и для ДНК-компьютеров. Кроме этого, встанет проблема точности измерений физических величин при вводе и выводе данных, или проблема точности изготовления самого устройства.

Сегодня наиболее точно физики умеют измерять частоту и время. В эталонах времени точность достигает 14 десятичных (47 двоичных) знаков. Но этого явно недостаточно даже для не слишком больших задач. Тем самым, надежды на то, что удастся придумать классическое устройство для решения проблемы перебора, представляются почти несбыточными. Вот и получается, что проблема перебора вряд ли имеет отношение к классической, непрерывной физике.

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

Мы уже упоминали алгоритм Шора. Этот алгоритм стимулировал работы по созданию квантовых компьютеров. О них уже писала Компьютерра. Но пока не ясно, может ли квантовый компьютер решить любую задачу перебора. Да и удастся ли практически реализовать такой компьютер? Проблема перебора иногда тесно связана с точностью измерений, или, что почти то же самое, хорошей изоляции системы от внешних помех. Это основная проблема и на пути создания квантовых компьютеров.

Хуже того, теория измерений и сегодня одно из наиболее темных мест квантовой механики. Любая система в квантовой механике всегда состоит как бы из двух частей: собственно квантовой системы и классического измерительного прибора. Беда в том, что граница между ними четко не определена. Никто не знает, где кончается квантовый объект и начинается классический прибор. Некоторые горячие головы даже считают, что эта граница проходит где-то между материальным миром и нашим сознанием ¹. В процессе измерения таинственным образом происходит выбор из порой большого количества альтернатив, вероятности которых и позволяет вычислить квантовая теория. Именно в квантовых системах природа как раз и решает что-то похожее на задачу перебора.

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

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