Как я уже говорил, развитие TCS происходит параллельно изменениям
в реальном компьютерном мире. Вряд ли кто-нибудь сейчас возьмется
всерьез предсказывать, скажем, состояние Интернета через пять лет;
точно так же и я не буду даже пытаться делать какие-либо
долгосрочные прогнозы относительно развития TCS. В этом
заключительном разделе читатель найдет всего лишь описание 
нескольких "точек роста", в которых в настоящий момент
происходят наиболее интересные вещи. Нет нужды повторять, что выбор
тем сильно обусловлен личными вкусами и пределами компетенции автора
и в основном концентрируется вокруг математического ядра TCS, то
есть теории сложности (классических) вычислений.
Первое, что необходимо отметить даже в нашем кратком обзоре, это
то, что проблема N1 в TCS переходит в XXI век. Читатель,
по-видимому, уже догадался, что я говорю о P=NP-проблеме,
которая, между прочим, в известном списке центральных нерешенных
задач всей математики [1] занимает почетное третье место, сразу вслед за
гипотезами Римана и Пуанкаре. Эта проблема удивительно многолика, и
одна из ее популярных формулировок состоит в следующем: можно ли в
общем случае устранить трудоемкий (то есть экспоненциальный
по n) перебор вариантов из произвольного алгоритма?
Более того, в настоящее время известны тысячи так называемых
NP-полных задач (возникающих в самых разных областях
человеческой деятельности), которые решаются очевидным "переборным"
алгоритмом и обладают тем свойством, что полиномиальный алгоритм для
любой из них влечет за собой полиномиальный алгоритм для
всех остальных.
Значительную часть современной TCS можно довольно успешно
классифицировать в соответствии с ее отношением к феномену перебора,
квинтэссенцией которого является P=NP-проблема. Наиболее
теоретические разделы этот феномен изучают, другие области основаны
на предположении, что PNNP, то есть устранение
перебора в общем случае невозможно. Наконец, в строгом соответствии
со знаменитым местом из Стругацких (о решении задач, не имеющих
решения) теоретики пытаются понять, что же делать, если
PNNP, а решать те или иные алгоритмические задачи все
равно надо.
Очень важная область, основанная на предположении, что
PNNP, - это современная криптография с открытым
ключом. Если противник имеет доступ к экспоненциальному перебору
вариантов (то есть, в частности, умеет разлагать числа на множители,
брать дискретный логарифм в конечном поле и т. д.), все известные
протоколы моментально теряют смысл. К сожалению, рассказ об этой
увлекательной дисциплине выходит далеко за рамки нашего эссе, и я
лишь могу порекомендовать книгу [2] для более подробного знакомства с предметом.
Наиболее бурно развивающаяся область, где специалисты пытаются
понять, что и как можно вычислить несмотря на неравенство
PNNP, - это, конечно, квантовые вычисления.
"Компьютерра" уже подробно писала о них (см. #224, 1997 г.), поэтому
я ограничусь лишь парой кратких замечаний. По-видимому, центральная
открытая проблема здесь состоит в получении внутреннего (то есть не
зависящего от принципов квантовой механики) описания всех тех
классических задач, которые можно эффективно решать на
квантовом компьютере.  Кроме
того, квантовые вычисления - пример благополучной области, в которой
теория и практика (которую пока, впрочем, в основном представляют
физики) гармонично взаимодействуют с взаимным уважением к интересам
и особенностям партнера. Результат, как говорится, налицо.
Совершенно фантастические результаты получаются в области
вероятностно проверяемых доказательств (PCP, от
Probabilistically Checkable Proofs) и их приложений к сложности
аппроксимации оптимизационных задач. Все началось с концепции
интерактивного доказательства (1987 г.), которая на самом
деле очень близка многим жизненным процессам. Представьте себе ответ
студента на устном экзамене преподавателю, которому лень проверять
знание доказательства целиком; вместо этого он подбрасывает монетку
и в соответствии с результатами бросания задает выборочные вопросы,
пытаясь поймать студента на противоречии. С помощью интерактивных
доказательств можно эффективно доказывать очень многие вещи, пока не
поддающиеся доказательствам обычным.
Это привело к целой революции в наших представлениях о том, что
такое доказательство вообще (кстати, довольно точно отражающей
возврат к изначальному древнегреческому определению "рассуждение,
которое убеждает") и, после довольно изрядной петли в развитии, к
так называемой основной PCP-теореме ( [0] содержит некоторые дополнительные детали).
Все это может показаться (и казалось до 1990 года) забавным, но
далеким от жизни занятием, пока не обнаружилось следующее. Большое
число переборных задач на самом деле являются задачами
оптимизации какой-либо целевой функции на множестве всех
допустимых решений. За редкими исключениями такие задачи вообще не
поддавались никакой классификации, пока не выяснилось, что
PCP-техника замечательно приспособлена для этой цели. За прошедшие
десять лет на ее основе фактически с нуля была создана стройная
схема классификации оптимизационных задач (с точки зрения их
приближенного решения), неизмеримо более богатая, чем обычная теория
NP-полноты, и пока изобилующая многочисленными белыми
пятнами. В процессе этой работы открываются новые важные алгоритмы;
я могу отметить в этой связи недавний алгоритм С. Ароры (S. Arora)
для приближенного решения задачи коммивояжера на плоскости.
По-видимому, от этой области в ближайшие годы можно ждать новых
сюрпризов.
Еще одна важная "точка роста" - это дерандомизация алгоритмов.
Многие алгоритмы (в частности, основанные на методе Монте-Карло)
существенно используют генераторы случайных чисел. Так как наличие
таких генераторов в природе - вещь далеко не саморазумеющаяся,
возникает естественный вопрос, в каких случаях их можно из алгоритма
устранить (полная дерандомизация) или хотя бы заменить генератором
псевдослучайных чисел, к которым предъявляются требования
менее строгие, чем полная случайность. Вот пример лишь одной
удивительной конструкции, экстракторов (от английского слова
"extract"), которую теоретики активно изучают в настоящее время.
Пусть у вас есть устройство, генерирующее n
псевдослучайных битов, про которые известно лишь одно: никакое
двоичное слово длины n не наблюдается со слишком большой
вероятностью. Это крайне слабое ограничение называется оценкой снизу
на слабую энтропию. Оказывается, что, используя в качестве
"катализатора" лишь порядка log n по-настоящему случайных
битов, можно "выжать" практически всю случайность, содержащуюся в
любом устройстве с достаточно большой слабой энтропией. Например,
можно построить битов, отличие которых от полностью случайных
экспоненциально мало. Такие конструкции и называются
экстракторами.
Наконец, к настоящему моменту стало понятно, что решить
P=NP-проблему одним наскоком, по-видимому, не удастся, и TCS
постепенно переходит к тому, что в таких случаях делают все
нормальные математики, то есть планомерной осаде и попыткам
проникнуть в суть трудностей, с которыми мы сталкиваемся.
Перспективной областью с этой точки зрения выглядит теория
сложности доказательств, которая, грубо говоря, изучает, какие
факты обладают эффективным (полиномиальной длины) и классическим
(без привлечения интерактивности) доказательством. Попытки
установить, что утверждение PNNP не обладает по
крайней мере эффективным доказательством (пока в этом направлении
есть лишь частные результаты), привели к более глубокому пониманию
природы самой проблемы, и примечательно, что все большую роль в этом
анализе играют генераторы псевдослучайных чисел.
Назад | Вперед
Написать комментарий
|
