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

Допустимость означает, что эта конфигурация действительно возникает при некотором начальном расположении мин. Именно проблема установления допустимости NP-полна, а доказательство получено путем сведения этой задачи к классической NP-полной проблеме SAT. Но самое интересное, разумеется, не «что», а «как».

Ричард Кей из Университета Бирмингема ( Richard Kaye ) свел «Сапера» к SaT следующим образом. В SaT речь идет о поведении булевой формулы, то есть схемы, реализуемой гейтами вида "И", «ИЛИ», «НЕ». Кей придумал несколько экзотических конфигураций «Сапера», которые напрямую в самом буквальном смысле реализуют гейты и соединяющие их проводники. Из таких конфигураций можно собрать любую логическую схему. По сути, игровое поле превращается в компьютер! Квадраты поля принимают значения T (есть мина) или F (нет мины). Проверка допустимости конфигураций, реализующих логические и другие конструктивные элементы, интерпретируется как выполнение соответствующих им функций. На рис. 1 показано, как устроен провод, на рис. 2 — вентиль "И" (оригиналы рисунков см. на сайте Кея).

NP-полны также задачи составления самых обыкновенных расписаний для школьников и студентов (невзирая на это одна из российских компаний, легко находимая «Гуглом», предлагает программу составления расписаний, получившую призы на целом ряде конкурсов; суха теория, мой друг, но древо жизни пышно зеленеет, как говаривал один коварный литературный персонаж).