Недавно группой ученых из Гарвардского университета было предложено новое устройство - жидкий компьютер для решения NP-полных задач за полиномиальное время. Статья с такими претензиями, да еще опубликованная в солидных трудах Национальной академии наук США заставляет специалистов хвататься одной рукой за сердце, а другой за кошелек. Но, вчитавшись и подумав, понимаешь, что пока ничего серьезного не произошло. И есть основания полагать, что - на пути создания аналоговых компьютеров для решения знаменитой задачи перебора - скорее всего и не произойдет. Но начнем по порядку.

«Компьютерра» уже писала о проблеме перебора - главной проблеме теории алгоритмов ¹. Напомню вкратце.

Известно много алгоритмических задач, некоторые из которых обманчиво просто формулируются, но все не поддаются современным компьютерам. Например, знаменитая задача коммивояжера - объехать n городов так, чтобы длина пути была минимальной. Алгоритм решения таких задач часто очевиден - решение может быть найдено прямым перебором вариантов ответов. Беда в том, что вариантов очень много - n! И если ваш компьютер решал задачу для 99 городов, например, за час, то для 100 городов ему потребуется четыре дня, а для 120 городов не хватит всех компьютеров мира и времени жизни Вселенной.

Математики, замученные упреками начальства в неспособности придумать хорошие алгоритмы для простых задач, в свое оправдание придумали теорию. Вместо того чтобы задачи решать, они стали изобретать быстрые алгоритмы, которые сводят одну такую задачу к другой. Быстрыми считаются алгоритмы, время счета которых растет как n в некоторой степени. Появилась железная отговорка. Я, мол, не могу придумать алгоритм для этой задачи, потому что она сводится к другой известной, которую пока не смог решить не один гений. Задача, к которой можно свести любую задачу перебора называется NP-полной ². Их накопились тысячи. И если хотя бы для одной из них будет придуман быстрый алгоритм, то почти автоматически он будет распространен на все остальные. И по мере роста количества нерешенных задач и потерпевших фиаско гениев крепнет общая убежденность (или заблуждение), что такого алгоритма просто не существует.

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

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

Предположим на минуту, что некий гениальный программист (а им можете стать Вы, читатель) придумал быстрый алгоритм для решения хотя бы одной из NP-полных задач. Или, быть может, придумал некоторое устройство, которое находит ответ. Такая возможность, в отличие от создания вечного двигателя, пока не исключена. К чему это приведет?

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

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

Короче говоря, если Вы, читатель, придумаете алгоритм, или устройство, решающее задачу перебора, то мировая слава, а при некоторой ловкости и очень большие деньги Вам обеспечены.

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

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

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

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

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

Окончание следует