Золотой билет. P, NP и границы возможного - Лэнс Фортноу

Комнаты в общежитии Королевского технологического рассчитаны на трех человек. Можно ли расселить студентов таким образом, чтобы в каждой комнате жили только друзья? NP-полная задача.

Судоку – это японская головоломка с числами. В классическом варианте используется квадратная сетка 9 × 9 (рис. 4.2).

Рис. 4.2. Классический вариант судоку

Рис. 4.3. Решение судоку из рис. 4.2

Цель игры – заполнить пустые клетки цифрами от 1 до 9 так, чтобы в каждой строке, каждом столбце и каждом жирно очерченном квадрате 3 × 3 эти цифры не повторялись.

Судоку лежит в классе NP, поскольку проверить имеющееся решение труда не составляет. Вы спросите, насколько сложно это решение найти? На самом деле все не так уж страшно: обычный среднестатистический компьютер при помощи простого перебора с возвратом решает классический вариант всего за несколько секунд.

А как обстоит дело с игрой на большом поле? Например, с сеткой 25 × 25, в которой каждая строка, каждый столбец и каждый мини-квадрат должны содержать все буквы от A до Y?

В этом случае вычисление займет уже гораздо больше времени, а с сеткой 100 × 100 вообще ни один современный компьютер не справится.

Рис. 4.4. Гигантское судоку

Поиск решения гигантского судоку – задача NP-полная. Считаете себя мастером судоку? Или знаете надежный способ решения какой-нибудь другой гигантской головоломки? Тогда в ваших руках ключ от решения задачи о выполнимости, задачи коммивояжера и тысячи других NP-полных проблем!

Есть еще много игр для одного игрока, решение которых представляет собой NP-полную задачу. Возьмем, к примеру, встроенного в Microsoft Windows «Сапера».

Рис. 4.5. «Сапер»

Число в ячейке говорит о количестве мин, расположенных в соседних с ней квадратиках – по вертикали, горизонтали и диагонали. Вы должны либо открыть ячейку, чтобы узнать это число, либо поставить на ней флажок, если думаете, что в ячейке бомба. Откроете бомбу – проиграете. Нахождение выигрышной стратегии в гигантском «Сапере» также представляет собой NP-полную задачу. На рисунке ниже показано расположение оставшихся бомб.

Другой пример – «Тетрис», в котором нужно передвигать и поворачивать фигурки так, чтобы образовывались сплошные горизонтальные ряды. Заполненный ряд тут же исчезает. Игра заканчивается, когда на экране больше не осталось свободных рядов; цель играющего – продержаться как можно дольше.

Фигурки бывают разных форм. В классическом варианте «Тетриса» вы не знаете, какая фигурка выпадет следующей. Впрочем, если бы вам даже заранее сообщили последовательность появления фигурок, выбор оптимальной стратегии все равно остался бы NP-полной задачей.

Рис. 4.6. Оставшиеся бомбы

Рис. 4.7. «Тетрис»

Кто бы мог подумать, что, научившись мастерски играть в судоку, «Тетрис» или «Сапер», можно доказать равенство P и NP и решить одну из задач тысячелетия!

Рис. 4.8. Виды фигурок в «Тетрисе»

Как насчет кубика Рубика? Наверняка это тоже NP-полная задача: ведь если даже освоение классического варианта 3 × 3 × 3 занимает столько времени, что уж говорить о больших кубах?

Рис. 4.9. Кубик Рубика. Фото: Том ван дер Занден

На самом деле все совсем не так. Благодаря такой области математики, как теория групп, у нас есть эффективные алгоритмы, способные справиться даже с гигантскими кубами. Оптимального решения они не дают, но все же позволяют собрать кубик относительно быстро вне зависимости от его начального состояния.

Верится с трудом, но это правда – кубик Рубика намного проще «Тетриса», «Сапера» и судоку.

А как обстоит дело с играми для двоих? Шахматы, шашки, го, «Отелло»? Если говорить о гигантских версиях, то они не уступают по сложности ни проблеме выполнимости, ни другим NP-полным задачам, однако к классу NP, тем не менее, не принадлежат. Вы спросите, почему? Потому что если я скажу, что белые обеспечат себе выигрыш, передвинув пешку на «e3», то вы вряд ли сможете быстро это проверить. Ученые полагают, что на самом деле эти игры намного труднее любой NP-полной задачи.

Почки выводят из организма балластные вещества. У большинства людей обе почки здоровы; если одна отказала, другая будет работать за двоих, позволяя человеку жить полноценной жизнью. Иногда отказывают обе почки, и тогда от смерти может спасти только регулярный диализ, который дорого стоит и отнимает много времени.

Если ваши почки здоровы, вы можете стать донором и отдать одну из них тому, у кого почки не функционируют вообще, – при условии совместимости с организмом реципиента. Совместимость проверяется с помощью несложного анализа крови.

Допустим, почки Элис вышли из строя. Ее муж, Боб, согласен стать донором. Если Боб пройдет тест на совместимость, врачи пересадят Элис его почку.

А если не пройдет? Тогда можно будет попытаться совершить обмен почками.

Предположим, Чарли требуется почка, его брат Дэвид готов отдать свою, но его почка не подходит. Если Дэвид совместим с Элис, а Боб – с Чарли, то можно провести операцию сразу на четырех пациентах, и в результате и Элис, и Чарли получат рабочую почку.