Математика жизни и смерти. 7 математических принципов, формирующих нашу жизнь

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

Чтобы провести аналогию, представьте, что вы собираете пазл из однообразного изображения, вроде картинки чистого голубого неба. Перепробовать все возможные комбинации кусочков, чтобы понять, подходят ли они друг другу, – трудная задача; сказать, что она займет много времени – это преуменьшение. Однако, как только пазл закончен, правильность его сборки проверить легко. Более строгие определения эффективности математические выражаются в описании того, насколько быстро работает алгоритм по мере усложнения проблемы – когда к пазлу добавляется больше кусочков. Набор задач, которые можно решить быстро (в так называемом полиномиальном времени), называется классом сложности P. Бóльшая группа задач, которые можно быстро проверить, но не обязательно можно быстро решить, называется классом сложности NP (что расшифровывается как недетерминированное полиномиальное время). Задачи типа P – это подмножество задач типа NP, так как, решив задачу быстро, мы автоматически проверяем найденное решение.

А теперь представьте, что нужно построить алгоритм собирания любого пазла. Если алгоритм входит в группу P, то время, затраченное на его решение, может зависеть от количества элементов пазла, квадрата, куба или даже большей степени этого числа. Например, если алгоритм зависит от квадрата количества элементов, то для сбора пазла из двух элементов может потребоваться 4 (2²) секунды, для сбора пазла из 10 элементов – 100 (10²) секунд, а для пазла из 100 элементов – 10 000 (100²) секунд. Этот отрезок времени кажется достаточно долгим, но он укладывается в считаные часы. Однако если алгоритм входит в группу NP, то с увеличением количества кусочков время, затрачиваемое на его решение, может вырасти по экспоненте. Если на сбор пазла из 2 элементов понадобятся те же 4 (2²) секунды, то на пазл из 10 элементов – уже 1024 (2¹⁰) секунды, а на пазл из 100 элементов – 1 267 650 600 228 229 401 496 703 205 376 (2¹⁰⁰) секунд, что значительно превышает время, прошедшее с момента Большого взрыва. Оба алгоритма требуют больше времени на исполнение с усложнением задачи (ростом количества элементов), но алгоритмы для решения общих проблем группы NP с усложнением задачи быстро становятся непригодными для ее решения. В сущности, литерой «P» можно было бы обозначать проблемы, Решаемые на практике, а литерами «NP» – Не Решаемые на практике.

Проблема «P vs NP» заключается в вопросе, все ли проблемы класса NP, решения которых можно быстро проверить, но алгоритм быстрого решения, которых неизвестен, действительно являются и членами класса P. Может быть, проблемы класса NP имеют практический алгоритм решения, но мы его просто еще не нашли? В математической терминологии, равны ли P и NP? Если да, то, как мы увидим, потенциал применения этого равенства – даже для решения повседневных задач – огромен.

•

Роб Флеминг, главный герой классического романа 90-х Ника Хорнби «Hi-Fi», – одержимый музыкой владелец магазина подержанных пластинок Championship Vinyl. Периодически Роб пересортировывает свою огромную коллекцию пластинок в разном порядке – по алфавиту, по хронологии и даже автобиографически (порядок, в котором он покупал свои пластинки, рассказывал историю его жизни). Сортировкой и составлением каталогов занимаются не только любители музыки в поисках катарсиса – это способ организации информации, позволяющий быстро сгруппировать ее в соответствии с необходимыми критериями и получить данные по конкретному запросу. Когда вы одним кликом группируете письма в своем электронном почтовом ящике по дате, отправителю или теме, ваш клиент электронной почты реализует эффективный алгоритм сортировки. eBay реализует алгоритм сортировки, когда вы выбираете категории товаров, соответствующих вашему поисковому запросу, переходя от «наилучшего соответствия», к «наименьшей цене» или «заканчивающиеся быстрее всего». После того как Google определит, насколько точно веб-страницы соответствуют заданным вами поисковым критериям, ему необходимо быстро отсортировать страницы и представить их вам в правильном порядке. Эффективные алгоритмы, позволяющие достичь этой цели, пользуются большим спросом.