NP-полнота и вычислительная неразрешимость

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

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

В самом начале книги, когда приводились первые основополагающие определения, мы договорились о том, что нашим рабочим критерием эффективности будет полиномиальное время выполнения.

Как упоминалось ранее, у такого конкретного определения есть одно важное преимущество: оно позволяет привести математическое доказательство того, что некоторые задачи не могут быть решены при помощи алгоритмов с полиномиальным временем (то есть «эффективных»).

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

Но для многих фундаментальных дискретных вычислительных задач (из области оптимизации, искусственного интеллекта, комбинаторики, логики и т. д.) этот вопрос оказался слишком сложным и с тех пор так и остается открытым: алгоритмы с полиномиальным временем для таких задач неизвестны, но и доказательств того, что таких алгоритмов не существует, пока нет.

В свете этой формальной неоднозначности, которая только укреплялась с течением времени, в области изучения вычислительной сложности был достигнут заметный прогресс.

Такие задачи называются NP-полными, — смысл этого термина вскоре станет более понятен. Существуют буквально тысячи NP-полных задач в самых разных областях; похоже, этот класс содержит значительную долю фундаментальных задач, сложность которых не поддается разрешению.

Формулировка NP-полноты и доказательство эквивалентности всех таких задач в действительности являются весьма значительным результатом: это означает, что все эти открытые вопросы в действительности представляют собой один открытый вопрос, один тип сложности, который мы пока не понимаем в полной мере.

С практической точки зрения NP-полнота фактически означает «запредельную вычислительную сложность, хотя мы пока не можем этого доказать». Доказательство того, что задача является NP-полной, становится веской причиной для прекращения поисков эффективного алгоритма.

С таким же успехом можно искать эффективный алгоритм для любой другой знаменитой вычислительной задачи, которая заведомо является NP-полной; многие ученые пытались найти эффективные алгоритмы для таких задач — но пока безуспешно.