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

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

Мой любимый пример – то, что я называю Шатром Матушки Мушки. Малышка Мушка парит в футе (в метре, в километре – на любой ненулевой высоте) над полом. Матушка Мушка хочет сшить шатер с основанием на полу, чтобы он прикрывал Малышку, и использовать при этом как можно меньше материи. Какой шатер имеет минимальную площадь? Если мы представим Малышку Мушку в виде точки, то ответ будет «такого шатра не существует». Сшить можно конический шатер любой ненулевой площади, если площадь нулевая, то это линия, а не шатер. Для любого заданного шатра существует другой, вдвое меньшей площади, который тоже выполняет свою задачу. Поэтому наименьшей площади не существует.

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

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

Главный вопрос звучит так: насколько быстро возрастает время вычислений (измеренное как число вычислительных шагов) в любом методе вычисления ответа в сравнении с объемом данных, необходимых для постановки задачи? То есть если для описания задачи необходимо n двоичных знаков, то как будет зависеть от n время вычислений? Для практичных алгоритмов время расчета обычно растет как степень n, скажем, n² или n³. Говорят, что эти алгоритмы выполняются за полиномиальное время. Символически их обозначают как класс P. Время выполнения непрактичных алгоритмов растет много быстрее, часто экспоненциально, как 2ⁿ или 10ⁿ. Алгоритм «просчитать все маршруты» для задачи коммивояжера примерно таков – он выполняется за факториальное время n!, которое растет быстрее любой экспоненты. В промежутке находится серая зона, где время выполнения больше любого полинома, но меньше экспоненты. Иногда такие алгоритмы практичны, иногда нет. В целях настоящей книги мы можем принять очень строгий взгляд и отправить их все в корзину с надписью «непрактичные».

Это не то же самое, что NP.

Эта аббревиатура обозначает куда более тонкое понятие: недетерминированное полиномиальное время. Это время выполнения алгоритма, который может решить, является ли каждое конкретное предложенное решение верным. Вспомним, что число называется простым, если не имеет других делителей, кроме 1 и самого себя, так что числа 2, 3, 5, 7, 11, 13 и т. д. являются простыми. В противном случае число называется составным. Так что 26 – составное число, поскольку равно 2 × 13. Числа 2 и 13 – простые сомножители числа 26. Предположим, что вы хотите найти простой делитель числа, состоящего из 200 десятичных знаков. Вы тратите год на безрезультатный поиск такого числа, а затем в отчаянии обращаетесь за советом к Дельфийскому оракулу. Оракул называет в качестве ответа конкретное большое число. Вы понятия не имеете, откуда оно взялось (в конце концов, оракул обладает волшебным даром предсказания), но вы можете сесть и подсчитать, действительно ли число, названное оракулом, разделит нацело то очень большое число, о котором шла речь. Такой расчет намного, намного проще, чем собственно поиск простого делителя.

Предположим, что всякий раз, когда оракул предлагает ответ, вы можете проверить его при помощи алгоритма с полиномиальным временем выполнения (P). Тогда сама задача относится к классу NP – недетерминированному полиномиальному. Задача оракула намного сложнее вашей, но вы всегда можете решить, верный ли ответ он вам дал.