Новый ум короля: О компьютерах, мышлении и законах физики

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

В задачах покрытия и задачах со словами, рассмотренных выше, можно уже уловить, как применяется подобный подход (хотя это не те области математики, где аппарат развит в достаточной степени). Мы смогли привести очень простое доказательство для того, чтобы показать невозможность трансформации одного слова в другое при помощи установленных правил. Нетрудно вообразить, что более «продвинутые» методы доказательства способны помочь в более сложных случаях. Не исключена вероятность, что эти новые подходы могут быть превращены в алгоритмические процедуры. Мы знаем, что ни одна процедура не может удовлетворять всем примерам задачи со словами, но те из них, которые ускользают из «алгоритмических сетей», должны быть очень тонко и аккуратно сконструированы. Конечно, как только мы узнаемпринцип построения таких примеров — как только мы будем уверены, что в неком конкретном случае произошла «осечка» алгоритма, — мы сможем усовершенствовать наш алгоритм так, чтобы он включал и этот частный пример. Ускользать могут только пары «неравных» слов, так что, как только мы находим такую «ускользающую» пару, мы можем быть уверены в их «неравенстве» и присовокупить этот критерий к нашему алгоритму. Так наше более глубокое понимание ведет ко все более совершенным алгоритмам!

Теория сложности

Рассуждения о природе, возможности построения, существования и ограничениях алгоритмов, которые я привел в предыдущих главах, были по большей части «нестрогими». Я совсем не касался вопроса о возможности практического применения упоминавшихся алгоритмов. Даже в тех задачах, где существование алгоритмов и возможные способы их построения очевидны, все же может потребоваться довольно много труда для их воплощения в нечто полезное с точки зрения практического использования. Иной раз небольшая догадка или искусный ход могут в значительной степени упростить алгоритм или же многократно увеличить его быстродействие. Техническая сторона этих вопросов часто бывает очень сложна, и в последние годы в различных направлениях прилагалось много усилий в области построения, понимания и совершенствования алгоритмов — быстро растущем и развивающемся поле деятельности для пытливых умов. Мне представляется не слишком уместным углубляться здесь в тонкости подобных вопросов. Однако, существует довольно много абсолютныхограничений общего характера (известных или предполагаемых) на возможное повышение быстродействия алгоритма. Оказывается, что среди алгоритмических по своей природе задач существуют определенные классы проблем, решать которые с помощью алгоритмов несоизмеримо труднее, чем остальные. Такие задачи можно решать только с помощью очень медленных алгоритмов (или, допустим, алгоритмов, требующих чрезмерно больших ресурсов для хранения информации, и т. п.). Теория, в которой рассматриваются подобные вопросы, носит название теории сложности.

Теория сложности занимается не столько изучением трудностей, связанных с решением отдельныхзадач, сколько с бесконечными семействами задач, в каждом из которых любая задача может быть решена с помощью одного и того же алгоритма. Различные задачи такого семейства будут отличаться по «размеру», который выражается некоторым натуральным числом п. (Чуть позднее я объясню более подробно, как фактически этот номер п характеризует размер задачи.) Время, требуемое для решения конкретной задачи из рассматриваемого класса, — а вернее, количество элементарных шагов, — дается некоторым числом N, зависящим от n. Для определенности договоримся, что N— это наибольшее число шагов среди всех задач данного размера n, которое может понадобиться алгоритму для решения. При этом, с ростом nувеличивается также и N. На самом деле, Nскорее всего будет расти гораздо быстрее n. Например, Nможет быть примерно пропорционально n², или n³или, скажем, 2ⁿ(которое при больших nзначительно превосходит n², n³n⁴, n⁵и, вообще, n^rдля любого фиксированного n), или даже  ₂2 ⁿ(которое, в свою очередь, растет еще быстрее).