Читать «Золотой билет» онлайн - страница 41
Лэнс Фотноу
Рис. 4.6. Оставшиеся бомбы
Рис. 4.7. «Тетрис»
Кто бы мог подумать, что, научившись мастерски играть в судоку, «Тетрис» или «Сапер», можно доказать равенство P и NP и решить одну из задач тысячелетия!
Рис. 4.8. Виды фигурок в «Тетрисе»
Как насчет кубика Рубика? Наверняка это тоже NP-полная задача: ведь если даже освоение классического варианта 3 × 3 × 3 занимает столько времени, что уж говорить о больших кубах?
Рис. 4.9. Кубик Рубика. Фото: Том ван дер Занден
На самом деле все совсем не так. Благодаря такой области математики, как теория групп, у нас есть эффективные алгоритмы, способные справиться даже с гигантскими кубами. Оптимального решения они не дают, но все же позволяют собрать кубик относительно быстро вне зависимости от его начального состояния.
Верится с трудом, но это правда – кубик Рубика намного проще «Тетриса», «Сапера» и судоку.
А как обстоит дело с играми для двоих? Шахматы, шашки, го, «Отелло»? Если говорить о гигантских версиях, то они не уступают по сложности ни проблеме выполнимости, ни другим NP-полным задачам, однако к классу NP, тем не менее, не принадлежат. Вы спросите, почему? Потому что если я скажу, что белые обеспечат себе выигрыш, передвинув пешку на «e3», то вы вряд ли сможете быстро это проверить. Ученые полагают, что на самом деле эти игры намного труднее любой NP-полной задачи.
Цепочка из почек
Почки выводят из организма балластные вещества. У большинства людей обе почки здоровы; если одна отказала, другая будет работать за двоих, позволяя человеку жить полноценной жизнью. Иногда отказывают обе почки, и тогда от смерти может спасти только регулярный диализ, который дорого стоит и отнимает много времени.
Если ваши почки здоровы, вы можете стать донором и отдать одну из них тому, у кого почки не функционируют вообще, – при условии совместимости с организмом реципиента. Совместимость проверяется с помощью несложного анализа крови.
Допустим, почки Элис вышли из строя. Ее муж, Боб, согласен стать донором. Если Боб пройдет тест на совместимость, врачи пересадят Элис его почку.
А если не пройдет? Тогда можно будет попытаться совершить обмен почками.
Предположим, Чарли требуется почка, его брат Дэвид готов отдать свою, но его почка не подходит. Если Дэвид совместим с Элис, а Боб – с Чарли, то можно провести операцию сразу на четырех пациентах, и в результате и Элис, и Чарли получат рабочую почку.
Представьте, что у нас имеется база данных с информацией по всем совместимым парам донор-реципиент. Тогда мы можем запустить на ней эффективный алгоритм, который найдет наибольшее возможное число обменов. Задача совсем не сложная и аналогична задаче о максимальном числе паросочетаний, рассмотренной в предыдущей главе.
Ограничиваться двумя парами за раз совсем не обязательно. В конце 2011 года силами шестидесяти хирургов была проведена цепочка из тридцати таких операций. Для тридцати человек это был единственный способ обрести здоровье.
Если мы в нашей базе разрешим обмен по цепочке, желая помочь как можно большему числу людей, то снова придем к NP-полной задаче. Равенство P и NP спасет чьи-то жизни, а это уже гораздо серьезнее, чем гарантированный выигрыш в игре «Сапер»!