Глава 8 WР-полнота и вычислительная неразрешимость

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

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

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

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

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

8.1.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Глава 8 WР-полнота и вычислительная неразрешимость:

  1. Глава III - ПОЛНОТА
  2. Полноте презирать тело, полноте шутить с ним!
  3. ГЛАВА III. ПОЛНОТА.
  4. О.А. Акулов Н.В. Медведев. Информатика и вычислительная техника, 2005
  5. Степанов А. Н.. Архитектура вычислительных систем и компьютерных сетей, 2007
  6. А.П. Пятибратов, Л.П. Гудыно, А.А. Кириченко. Вычислительные машины, сети и телекоммуникационные системы, 2009
  7. Осмотр средств вычислительной техники
  8. Полнота и пустота
  9. Полнота и пустота
  10. Пустота и полнота
  11. Пустота и полнота
  12. Пустота и полнота
  13. ПОЛНОТА См. статью ОЖИРЕНИЕ.
  14. 3.2. Ошибки в стремлении к полноте
  15. Пустота и полнота
  16. 3.1. ОЦЕНКА ПОЛНОТЫ
  17. 3.2. ОШИБКИ В СТРЕМЛЕНИИ К ПОЛНОТЕ