гилшрамме, ни и по любой ее (пусть небольшой) части. Аналогичным образом, каждое утверждение голографического доказательства (ГГД) содержит информацию о всем доказательстве в целом! Из этого следует, что ошибка на одной из линий (утверждений) голограммы с высокой степенью вероятности отразится на каждой линии ГГД. Более того! Перевод выкладок в форму ГГД при наличии нескольких ошибок усиливает их влияние на общий вид доказательства и делает более заметными. Это — как вы сами, наверное, догадались,— безмерно упрощает процедуру проверки: достаточно разобраться, скажем, с несколькими десятками, на худой конец — с сотней утверждений, вне зависимости от общей длины доказательства... и дело сделано.

Наш Айзек, неколебимо уверенный в собственной правоте, вручает ГГД редактору соответствующего журнала; последний вызывает скромного рецензента (фамилию которого никак не удосужится запомнить) и поручает разобраться... Скромный безымянный рецензент с помощью скромного ПК быстро проверяет доказательство — и ГИП-ГИП-УРА! Уравнение Снарка становится георемой Фермакса...

Сей оптимистический сценарий на первый взгляд кажется чистейшей фантастикой — однако это не так. Даже совсем не так: ведь буквально за считанные годы под него подвела солидную базу наука, называемая... Вот и первая трудность: в русском языке не обнаружилось термина, точно соответствующего англоязычному понятию THEORETICAL COMPUTER SCIENCE. Будем говорить о ТЕОРИИ ЧИСЛЕННЫХ МЕТОДОВ (ТЧМ) - не забывая, что речь идет о компьютерных вычислениях.

Итак, лет десять тому назад наука ТЧМ, как-то вдруг рванувшись вперед, вошла в тот ритм, который втянувшиеся специалисты именуют «гонкой, захватывающей дух». Еще говорят — «скачки с препятствиями», и последнее не лишено буквального смысла: теоретики начали перемахивать через ограничения, которые традиционным путем обойти АБСОЛЮТНО НЕВОЗМОЖНО.

t

Рассмотрим простенький пример. Существует некая группа людей (множество М), свя занных эмоциональными отношениями «нравится» и «не нравится»: субъекту А нравится субъект Б и не нравятся В и Г; Б терпеть не может А, равнодушен к В (т.е. не связан с ним эмоционально!), но обожает Г; В любит всех, а Г — никого... И тому подобное. Задача (известная как «проблема клики») состоит в гом, чтобы найти наибольшее подмножество (М') множества М, все элементы которого связаны симметричным отношением «взаимной приязни». То есть попросту надо выделить из исходной группы тех ее членов (не пропустив ни одного), которые неплохо относятся друг к другу. Для нашего четырехэлементного М, на котором заданы вышеописанные отношения, М' представляет пустое множество — взаимности в данной группе не су

ществует... Это очень просто выяснить, нарисовав соответствующий граф — геометрическую схему, на которой показано, как множество точек — вершин, или узлов графа — соединено попарно множеством непрерывных линий — ребер, или иначе дуг (в нашем случае вершины соединяются стрелками, и такой граф называется направленным). Если М содержит сотни элементов, го на бумаге уже не разберешься — приходится писать программу для компьютера. А если тысячи?

На основании накопленного опыта математики утверждают, что существуют «разумно ограниченные» проблемы, для которых тем не менее невозможно построить алгоритм, вычисляющий абсолютно точный ответ за «разумный период времени». Это изящное выражение может означать что угодно — от нескольких лет до... «Насколько мы можем оценить, решение графов с несколькими тысячами узлов требует времени, сравнимого или даже большего, чем срок существования нашей Вселенной», — поясняет Ласло Бабаи (Чикагский университет). Делу не поможешь, даже обратив все атомы Вселенной в элементы ультрасуперкомпьютера, который будет производить столько операций в секунду, сколько поперечников атома сможет преодолеть свет за то же время... «Проблема клики» — типичный представитель данного класса задач; теоретики показали, что — при большом разнообразии — все проблемы, требующие поиска оптимальной стратегии при наличии большого числа возможных выборов, имеют одинаковый уровень сложности.

Практические задачи, которые можно представить в виде многоузловых графов, постоянно возникают в жономике, планировании перевозок, при развитии телефонных сетей, в конструкторской работе и т. п. Выход найден в гом, что жертвуют точностью ради скорости, подсчитав на компьютере удовлетворяющий определенным критериям ПРИБЛИЗИТЕЛЬНЫЙ ОТВЕТ в относительно короткие сроки. Однако совсем недавно группа американских ТЧМ-математиков получила шокирующие результаты. Имена их стоит перечислить: это Карстен Лунд и Марио Шегеди (AT&T Bell Laboratories), Раджив Мотвани (Стэнфорд-ский университет), а также Санджив Арора и Мадху Судан (тогда студенты в Беркли). Они доказали, что для весьма значительного подкласса сложных проблем оптимизации НЕЛЬЗЯ ГАРАНТИРОВАТЬ ДАЖЕ ПРИБЛИЗИТЕЛЬНОГО ОТВЕТА за разумный период времени. На практике это означает, что решить любую аппроксимацию ничуть не проше, чем исходную задачу! Кроме того, конечная эффективность многих подходов к решению проблем по-пре-жнему неясна и дожидается своей оценки

«Этот результат не поможет вам в решении конкретной проблемы; он не дает алгоритма, с помощью которого можно работать быстрее. И все же он чрезвычайно полезен — указывая, что действительно можно сделать, а о чем нельзя даже мечтать. Самое замечательное в том, что ясному пониманию проблем реального мира способствовали высокотеоретические соображения, порожденные полетом фантазии» — гакова оценка Дэвида С. Джонсона (AT&T Bell Laboratories).

Тупиковая ситуация: конечные, разумно ограниченные задачи теоретически имеют абсолютно точные ответы, которые тем не

менее практически недостижимы Существует, правда, универсальный рецепт, изложенный в популярной песенке: «Нормальные герои всегда идут в обход...». Ему и последовала ТЧМ

ы

Толчком к развитию событий послужило рождение непривычного, шокировавшего многих математиков концепта ИНТЕРАКТИВНОГО ДОКАЗАТЕЛЬСТВА. Что такое математическое доказательство в традиционном смысле слова, представляет каждый старшеклассник (более или менее). Новая техника математики основана на случайном выборе и специфическом интерактивном взаимодействии «доказывающего» и «контролера». «Это совершенно ново и ни на что не похоже: одна сторона может убедить другую в том, что доказательство практически безупречно, с помощью процедуры, включающей случайный выбор — бросание монеты — и интерактивную игру-диалог»,— говорит Мануэль Блам из Калифорнийского университета, который сыграл ведущую роль в развитии революционного направления ТЧМ. Итак, теоретики получили новую парадигму, быстро продемонстрировавшую свою мощь.

Несколько лет назад, опираясь на концепцию Блама, ТЧМ-ученые разработали еще более удивительную идею, получившую название ДОКАЗАТЕЛЬСТВА ПРИ НУЛЕВОМ ЗНАНИИ. Суть ее - в обмене сторон «интуитивными ударами»: подобная схема, базирующаяся на встречной интуиции, дает возможность доказывающему убедить противную сторону в том, что данная конкретная георема справедлива — не сообщая ровным счетом ничего о самом методе доказательства С!). Если вы принадлежите к непосвященному большинству, трудновато осознать, что )то тоже строгая наука математика...

Тем временем Блам занялся новой проблемой, которую он обозначил как ПРОВЕРКУ РЕЗУЛЬТАТА (ПР) или же ПРОВЕРКУ ПРОГРАММЫ (ПП) При компьютерных вычислениях встает принципиальный вопрос: можно ли доверять программе — а следовательно, и полученному результату? Ведь в ней бывают скрытые ошибки (программисты называют их «багами», от английского «клоп, жучок»), да и аппаратное обеспечение зачастую не на высоте. Существуют два традиционных способа проверки. Во-первых, математически доказать, что данная программа работает безошибочно для всех мыслимых входных ланных; как правило, это весьма сложно — если вообще осуществимо. Путь второй: программу проверяют, вводя различные исходные данные; в этом случае нет никакой уверенности, что тестирование пере

28