Компьютерра - Журнал «Компьютерра» № 6 от 14 февраля 2006 года
Теперь, когда мы поняли формулировку задачи, перейдем к ее обсуждению.
Первое: почему она так сложна? Конечно, можно сказать «потому что вот уже полвека пытаются и никак не могут», но есть и более интересные и глубокие причины. Я уже упоминал в сноске, что если рассмотреть «классы с оракулами», то для разных оракулов ответ получится разным. Переход от обычных классов к классам с произвольными оракулами называется релятивизацией. Большинство существующих идей и методов доказательства теорем в теории сложности вычислений выдерживают релятивизацию, то есть могут быть обобщены на случай произвольного оракула. Стало быть, все эти идеи и методы для доказательства (не)равенства P и NP неприменимы! Более того, в 1996 году Александр Разборов (наш соотечественник, лауреат премии Неванлинны) и Стивен Рудих (Steven Rudich) ввели класс так называемых естественных доказательств и показали, что нет естественных доказательств, которые бы позволили доказать, что SAT не решается за полиномиальное время. Под впечатлением таких результатов некоторые математики начинают склоняться к тому, что несовпадение P и NP может оказаться недоказуемым в рамках существующей аксиоматики. В 2002 году проводился даже опрос на эту тему. Из ста исследователей на вопрос «как вы считаете, равны ли P и NP?» 61 ответил «нет», 9 — «да», 22 — «сомневаюсь» и 8 — «наверное, вопрос не зависит от существующей аксиоматики».
Второе: что будет следовать из различных решений этой задачи. Если P не равно NP, все в порядке. Небо не упадет на землю, Запад не сойдется с Востоком, а пришествие Зверя будет отложено до лучших времен. А вот если P=NP, то начнется такое… Практика показывает: на деле «полиномиальное» означает «относительно легко решаемое». И если появятся способы относительно быстро решать NP-полные проблемы — могут возникнуть очень серьезные проблемы уже вне математики. Например, современная практическая криптография, основанная на RSA или DES/AES, окажется бесполезной. К чему это приведет, любой человек, знакомый с тем, как нынче хранится защищенная информация (номер вашей банковской карточки, пароль к вашему почтовому ящику и т. п.), легко может себе представить. Кроме того, это повлечет за собой серьезные изменения в наших представлениях об иерархии сложностных классов: целый бесконечный набор классов, которые сейчас считаются разными — так называемая полиномиальная иерархия, — «схлопнется» до одного-единственного класса P, и многие другие весьма правдоподобные предположения окажутся неверными. И все же, в отличие от гипотезы Римана, здесь нельзя сбрасывать со счетов вероятность того, что классы окажутся равными: уже много открытий чудных приготовила нам теория сложности, и как знать — может быть, наша уверенность в том, что P не равно NP, — тоже не более чем иллюзия…
Подведем итоги. Проблема равенства или неравенства классов P и NP — одна из центральных проблем современной информатики. Как мы только что видели, на предположении о неравенстве этих классов держится очень большая часть повседневной практической безопасности каждого из нас. Так что миллион за такую проблему — совсем не много, пусть даже платят за любое из двух решений — что за «равно», что за «не равно»[Правда, я не знаю, заплатят ли миллион за доказательство того, что это (не)равенство нельзя доказать. Думаю, да]. А еще эта проблема, наверное, одна из самых доступных для понимания непрофессионального математика — что порождает поток дилетантских, очевидно неверных решений. Надеюсь, читатели «КТ» будут умнее и если уж и придумают решение, то такое, чтобы о нем стоило написать отдельную подробную статью, а лучше — книгу.
NP-полнота как генератор драйва
Cреди NP-полных задач есть и более веселые экземпляры, нежели упоминаемые в статье Сергея Николенко классические проблемы математики. Оказывается, точно такой же полнотой обладают и стратегии некоторых популярных игр. Самые яркие примеры: «Тетрис» и «Сапер» (он же «Минер», «Minesweeper»), пожирающие с одинаковым аппетитом что рабочее, что свободное время. Связаны ли гипнотизирующие свойства игр с (предполагаемым) отсутствием для них простого алгоритма победы — вопрос из области психологии, а психологи, как известно, не склонны к однозначным ответам. Но не так давно было строго математически доказано: нахождение полиномиальных алгоритмов для этих игр повлечет снятие вопросительного знака в гипотезе P=?NP, а стало быть, и падение современной криптографии (по крайней мере, концептуально). В этом смысле «Тетрис» и «Сапер» ничем не хуже зловещего коммивояжера, согласного двигаться лишь по наиболее дешевому маршруту.
NP-полны многие задачи, связанные с даже не с обычным, а с сильно упрощенным офлайновым «Тетрисом», когда поток фигурок, валящихся с потолка, заранее известен, а каждую фигурку можно переворачивать и двигать сколько угодно раз. Среди этих задач — максимизация числа заполненных строк, а также минимизация высоты, на которой в процессе игры находится самый верхний квадратик уже уложенных фигурок (подробнее см. работу исследователей из MIT, arXiv:cs:CC/0210020).
Очень красиво доказывается NP-полнота стратегического планирования для «Сапера». Стратегия в нем основана на решении такой задачи — выяснить, допустима ли заданная конфигурация игры, то есть расстановка цифр, флажков, открытых и закрытых квадратиков (игра идет на поле произвольного размера). Допустимость означает, что эта конфигурация действительно возникает при некотором начальном расположении мин. Именно проблема установления допустимости NP-полна, а доказательство получено путем сведения этой задачи к классической NP-полной проблеме SAT. Но самое интересное, разумеется, не «что», а «как».
Ричард Кей из Университета Бирмингема (Richard Kaye) свел «Сапера» к SaT следующим образом. В SaT речь идет о поведении булевой формулы, то есть схемы, реализуемой гейтами вида "И", «ИЛИ», «НЕ». Кей придумал несколько экзотических конфигураций «Сапера», которые напрямую в самом буквальном смысле реализуют гейты и соединяющие их проводники. Из таких конфигураций можно собрать любую логическую схему. По сути, игровое поле превращается в компьютер! Квадраты поля принимают значения T (есть мина) или F (нет мины). Проверка допустимости конфигураций, реализующих логические и другие конструктивные элементы, интерпретируется как выполнение соответствующих им функций. На рис. 1 показано, как устроен провод, на рис. 2 — вентиль "И" (оригиналы рисунков см. на сайте Кея).
NP-полны также задачи составления самых обыкновенных расписаний для школьников и студентов (невзирая на это одна из российских компаний, легко находимая «Гуглом», предлагает программу составления расписаний, получившую призы на целом ряде конкурсов; суха теория, мой друг, но древо жизни пышно зеленеет, как говаривал один коварный литературный персонаж).
Таковы же и задачи оптимальной стратегии на рынке труда, частный случай которых — чисто математически, конечно, — подбор оптимальных супружеских пар по объявлениям. Короче говоря, что в игре, что в жизни примитивный (ну хорошо, полиномиальный) просчет ситуаций, что называется, не катит, и это отчасти обнадеживает.
Но только если P не равно NP!
Литература
[1] www.claymath.org/millennium/P_vs_NP
[2] en.wikipedia.org/wiki/Complexi-ty_classes_P_and_NP
style="text-transform: uppercase;">ПИСЬМОНОСЕЦ
Автор: Илья Щуров Voyager
Здравствуй, уважаемая Терра!
Являюсь вашим читателем уже два года. Читаю журнал не всегда, но практически от корки до корки, особенно меня интересует OpenSource/Freeware software и Linux. Я линуксоид, и поэтому сторонник лицензионного софта, и наличие подобных статей радует, даже если они о freeware-программах для Windows. Приятно видеть, что вы информируете население о наличии таких альтернатив и возможности их использования вместо дорогих и почти всегда ворованных программ.
Поэтому понятно, я думаю, мое возмущение статьей «Бум грувить!» в номере 1-2 этого года. Ведь то, что там описано, фактически перечеркивает все ваши достижения. Да, и в ранних публикациях там часто были описаны платные софтинки, но до этого момента я не наблюдал такого (может, и было — не знаю, не видел) — описания программ стоимостью уже не 25—50 вечнозеленых, а под несколько сотен баксов (которые, понятно, почти никто не сможет купить, да и автор, скорее всего, искал кряк, не так ли?). Причем не каких-то довольно экзотичных, а самых что ни на есть распространенных программ профессионального класса.
Да еще как про них написано! Не просто как про дополнительную рекомендацию к более дешевым аналогам, а именно как про основные. Уже за это можно смертельно обидеться на господина Голубицкого. А на слова, что «цена для нашего человека еще не повод для беспокойства» вообще, уж простите, хочется ответить «современным» языком «Аффтар, выпей йаду»!
Это что же получается: мало того что не замечают более доступный софт, еще и «наговаривают» на «наших» людей, забывая, что среди них есть не только «обычные», но и те, кто по мере сил стараются использовать свободный софт или вообще переходят на Linux. А многие из-за таких вот статей и вовсе не знают об альтернативах. Это просто возмутительно — использовать профессиональный софт, несмотря на то что он обладает «излишней навороченностью», оправдывая это тем, что «качество звука у тяжеловесов на порядок выше, чем у “шкурок с мастерками”». Ценность этой статьи— нулевая, так как и так понятно, что «профессионалы» лучше «шароваров», а вот достойного выбора из последних не рассматривается, что было бы гораздо ценнее. А то, что статья носит вредительский характер, я думаю и так понятно. Короче, непонятно, что происходит: то ли вы действительно считаете вполне нормальным наличие профессиональных программ огромной стоимости на десктопах вовсе непрофессиональных в данной сфере пользователей, то ли просто не хватает авторов freeware’ного софта. Обидно, чес слово.
