В середине 1960-х годов Эдмондс, сотрудник Национального института стандартов и технологии, и Алан Кобхэм из IBM сформулировали рабочее определение того, что делает задачу решаемой или наоборот. Они доказывали утверждение, ныне известное как гипотеза Кобхэма и Эдмондса: алгоритм считается эффективным, если его действие происходит в так называемом полиномиальном времени, а именно O(n2), O(n3) или, в сущности, n в любой степени. Задача, в свою очередь, считается решаемой, если мы знаем, как решить ее, используя эффективный алгоритм. Задача, которую мы не можем решить в полиномиальном времени, напротив, считается нерешаемой. И везде, кроме мельчайших масштабов, нерешаемые задачи не поддаются решению с помощью компьютеров, какими бы мощными они ни были.

Таким образом, измерить сложность задачи возможно. Но какие-то задачи просто… сложные.

И чем же заканчивается тогда история с задачей о коммивояжере? Довольно любопытно, что мы до сих пор в этом не уверены. В 1972 году профессор Университета Беркли Ричард Карп продемонстрировал, что задача о коммивояжере связана со спорно пограничным классом задач, которые еще не были определены как решаемые или нерешаемые. Но пока что эффективных решений этих задач найдено не было (что делает их, по сути, нерешаемыми), и большинство программистов считают, что решений не найти. Таким образом, результат, свидетельствующий о невозможности решения задачи о коммивояжере, о котором говорил Флад в 1950-е годы, оказался фатальным. Более того, многие другие задачи по оптимизации, касающиеся всевозможных вопросов от политической стратегии до здравоохранения и пожарной безопасности, аналогичным образом попадают в класс нерешаемых.

Но для программистов, которые продолжают искать ответ, такой вердикт – вовсе не конец истории. Наоборот, для многих это призыв к действию. Вы же не можете просто опустить руки, определив, что проблема не имеет решения. Как говорил эксперт в области планирования Ян Карел Ленстра, «если задача трудная, это не значит, что вы можете забыть о ней. Это означает, что она просто находится в другом статусе. Это серьезный враг, но вы все равно должны бороться». И здесь мы приходим к бесценному выводу относительно того, как лучше всего подходить к задачам, где оптимальные решения недоступны. Как расслабиться.