Журнал «Компьютерра» № 6 от 14 февраля 2006 года

Очень красиво доказывается 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’ного софта. Обидно, чес слово.

С уважением,

Q, ваш непостоянный читатель