2), O(
n3) или, в сущности,
n в любой степени. Задача, в свою очередь, считается решаемой, если мы знаем, как решить ее, используя эффективный алгоритм. Задача, которую мы не можем решить в полиномиальном времени, напротив, считается нерешаемой. И везде, кроме мельчайших масштабов, нерешаемые задачи не поддаются решению с помощью компьютеров, какими бы мощными они ни были
[27].
Таким образом, измерить сложность задачи возможно. Но какие-то задачи просто… сложные.
И чем же заканчивается тогда история с задачей о коммивояжере? Довольно любопытно, что мы до сих пор в этом не уверены. В 1972 году профессор Университета Беркли Ричард Карп продемонстрировал, что задача о коммивояжере связана со спорно пограничным классом задач, которые еще не были определены как решаемые или нерешаемые. Но пока что эффективных решений этих задач найдено не было (что делает их, по сути, нерешаемыми), и большинство программистов считают, что решений не найти. Таким образом, результат, свидетельствующий о невозможности решения задачи о коммивояжере, о котором говорил Флад в 1950-е годы, оказался фатальным. Более того, многие другие задачи по оптимизации, касающиеся всевозможных вопросов от политической стратегии до здравоохранения и пожарной безопасности, аналогичным образом попадают в класс нерешаемых.
Но для программистов, которые продолжают искать ответ, такой вердикт – вовсе не конец истории. Наоборот, для многих это призыв к действию. Вы же не можете просто опустить руки, определив, что проблема не имеет решения. Как говорил эксперт в области планирования Ян Карел Ленстра, «если задача трудная, это не значит, что вы можете забыть о ней. Это означает, что она просто находится в другом статусе. Это серьезный враг, но вы все равно должны бороться». И здесь мы приходим к бесценному выводу относительно того, как лучше всего подходить к задачам, где оптимальные решения недоступны. Как расслабиться.
Лучшее – враг хорошего.
Вольтер
Когда кто-то советует вам расслабиться, это, вероятно, происходит потому, что вы слишком напряжены – придаете чему-то большее значение, чем следовало бы. Когда программисты сталкиваются со сложной задачей, они также прибегают к релаксации, делясь друг с другом такими книгами, как «Введение в методы релаксации» или «Техники дискретной релаксации». Но они не расслабляются сами, они ослабляют проблему.
Одна из самых простых форм релаксации в компьютерной науке – это смягчение ограничений. Согласно этому методу исследователи убирают ряд ограничений из задачи и приступают к решению получившейся задачи. Затем, по мере достижения некоторых успехов, они пытаются снова добавить эти ограничения. То есть они временно делают задачу проще в решении, прежде чем вернуть ее к реальности.