Это база: Зачем нужна математика в повседневной жизни

Очевидно, что проверка предложенного ответа должна быть намного проще его отыскания. Проверить, спрятано ли сокровище в месте, отмеченном крестиком на карте, намного проще, чем выяснить, где этот крестик должен стоять. Или возьмем математический пример: почти все верят, что нахождение простых делителей намного сложнее, чем проверка, является ли делителем данное простое число. В пользу этого свидетельствует, в частности, то серьезное обстоятельство, что быстрые алгоритмы проверки любого предложенного делителя известны, а их поиска – нет. Если P = NP, то для любой задачи, имеющей быстро проверяемый ответ, найти ответ тоже быстро. Это звучит слишком хорошо, чтобы быть правдой, и опыт математиков в решении задач говорит прямо противоположное. Поэтому почти все убеждены, что P ≠ NP.

Однако все попытки доказать это – или опровергнуть – зашли в тупик. Вы можете доказать, что задача принадлежит к классу NP, записав детальный алгоритм и подсчитав время его выполнения, но для доказательства того, что задача не относится к классу P, вам придется рассмотреть все возможные алгоритмы ее решения и показать, что ни один из них не относится к классу P. Как это сделать? Никто не знает.

Из этих попыток проистекает тот любопытный факт, что в одну и ту же категорию попадает огромное число задач-кандидатов. Все эти задачи относятся к NP. Более того, если для какой-то из них можно доказать, что она не принадлежит P, то и все остальные не принадлежат P. Они живут или умирают вместе. Подобные задачи называют NP-полными. Связанную с ними более крупную категорию называют NP-трудными задачами: она состоит из алгоритмов, способных эмулировать решение любой NP-задачи за полиномиальное время. Если выяснится, что данный алгоритм выполняется за полиномиальное время, это автоматически докажет, что то же верно для любой NP-задачи. В 1979 году Майкл Гэри и Дэвид Джонсон доказали, что задача коммивояжера относится к классу NP-трудных{22}. Если P ≠ NP, то любой алгоритм для ее решения потребует время выполнения, превышающее полиномиальное.

Флуд был прав.

* * *

Это, впрочем, не повод опускать руки, потому что существует по крайней мере два потенциально возможных пути вперед.

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

В 1980 году рекорд составлял 318 городов; к 1987 году их уже было 2392. К 1994 году рекорд увеличился до 7397 городов и ответ потребовал около трех лет вычислительного времени сети очень мощных компьютеров. В 2001 году точное решение для 15 112 немецких городов было получено с использованием сети из 110 процессоров. На обычном настольном компьютере этот расчет занял бы более 20 лет. В 2004 году задача коммивояжера была решена для маршрута по 24 978 городам Швеции. В 2005 году группа Concorde TSP Solver решила задачу коммивояжера для маршрута по 33 810 точкам на печатной плате. Рекорды не единственный мотив для таких исследований: методы, использованные в рекордных достижениях, работают необычайно быстро при решении менее масштабных задач. Задачу при числе городов не более сотни обычно можно решить за несколько минут, а не более тысячи – за несколько часов на типовом настольном компьютере.

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

* * *