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

Подавляющее большинство математиков считают, что P и NP – это принципиально разные классы проблем и что у нас никогда не будет быстрых алгоритмов для коммивояжеров или маршрутизации транспортных средств. Возможно, это к лучшему. Задача принятия решения с бинарным вариантом ответа для проблемы коммивояжера – канонический пример подгруппы задач, известной как NP-полные. Существует мощная теорема [156] Мощными называются теоремы, применимые в большом количестве разных систем (этот полуофициальный термин, как правило, применяется в отношении абстрактных алгебраических теорем). – Прим. пер. , утверждающая, что, если бы существовал практический алгоритм, способный решить одну NP-полную задачу, его можно было бы преобразовать для решения любой другой NP-задачи. Если эта теорема верна, она доказывала бы, что P равно NP – что P– и NP-задачи фактически являются одним и тем же классом задач. Поскольку почти вся криптография в интернете полагается на сложность решения определенных NP задач, доказательство того, что P равно NP, может быть губительным для онлайн-безопасности.

С другой стороны, тогда мы могли бы разработать быстрые алгоритмы для решения всевозможных логистических задач. Фабрики могли бы организовать производственный процесс с максимальной эффективностью, а службы доставки находили бы самые эффективные маршруты транспортировки, что потенциально снижало бы цену товара – даже если его больше нельзя было бы безопасно заказать онлайн! В научной сфере доказательство равенства P и NP может обеспечить эффективные методы машинного распознавания образов, генетического секвенирования и даже прогнозирования стихийных бедствий.

По иронии судьбы от равенства P и NP больше всего может выиграть наука, а вот сами ученые могут оказаться главными проигравшими. Некоторыми потрясающими научными открытиями человечество обязано прежде всего творческому мышлению высококвалифицированных и глубоко преданных своему делу людей: дарвиновская теория эволюции путем естественного отбора, доказательство Последней теоремы Ферма Эндрю Уайлсом, теория общей относительности Эйнштейна, ньютоновские уравнения движения. Если бы P равнялся NP, то компьютеры сумели бы найти формальные доказательства любой доказуемой математической теоремы – и многие из величайших интеллектуальных достижений человечества могли бы быть воспроизведены и вытеснены работой робота. Масса математиков остались бы без работы. По сути своей, проблема P vs NP – это очень непростая попытка выяснить, можно ли автоматизировать человеческое творчество.

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

Одно из семейств таких алгоритмов называется жадными алгоритмами. Эти краткосрочные процедуры нацелены на поиск лучшего локального выбора в попытке найти глобально оптимальные решения. Несмотря на то, что они работают быстро и эффективно, они не гарантируют получение оптимального или даже хорошего решения. Представьте, что вы впервые оказались в какой-то местности и хотите подняться на самый высокий холм, чтобы осмотреться. Жадный алгоритм подъема на вершину сводится к тому, чтобы сначала найти самый крутой уклон по отношению к вашей текущей позиции, а затем сделать шаг в этом направлении. На каждом шаге эта процедура повторяется до тех пор, пока вы не окажетесь в точке, по всем направлениям от которой будут лишь скаты. Это означает, что вы достигли вершины холма – но не обязательно самого высокого холма вокруг. Жадный алгоритм не гарантирует, что вы подниметесь на самую высокую вершину, с которой открывается наилучший вид. Возможно, что маршрут к вершине небольшого холма, на который вы только что взобрались, просто начинался круче, чем тот, который привел бы вас к вершине местного горного хребта, а выбор ошибочного маршрута был продиктован вашей эвристической близорукостью. Жадные алгоритмы могут найти решения, но не всегда гарантированно лучшие. Однако для проблем определенного типа жадные алгоритмы оптимальны.