Эффективная сертификация и определение NP

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

Вспомните, что в главе 1, при первом знакомстве с задачей о независимом множестве, мы спрашивали: можно ли сказать хоть что-нибудь положительное о сложности задачи (с вычислительной точки зрения)? И действительно, кое-что положительное нашлось: если граф содержит независимое множество с размером не менее к, то этот факт можно легко доказать, представив такое независимое мно- жество. Аналогичным образом, если экземпляр 3-SAT является выполнимым, это можно доказать, представив выполняющее присваивание. Поиск такого присваива- ния может быть невероятно сложной задачей, но после того, как сложная работа по его поиску будет завершена, остается подставить значения в условия и убедиться в том, что все они выполняются.

Здесь важен контраст между поиском решения и проверкой предложенного ре- шения. Для задачи о независимом множестве или 3-SAT алгоритм поиска решений с полиномиальным временем нам неизвестен; однако проверка предлагаемого ре- шения таких задач легко выполняется за полиномиальное время. Чтобы понять, что эта проблема не так уж тривиальна, представьте, какая проблема возникла бы, если бы потребовалось доказать невыполнимость экземпляра задачи 3-SAT. Какие «до- казательства» можно было бы предъявить, чтобы убедить вас за полиномиальное время в невыполнимости задачи?

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

Еще по теме Эффективная сертификация и определение NP:

  1. 1.4. Лицензирование, стандартизация и сертификация
  2. 1.4.3. Сертификация
  3. ЭФФЕКТИВНОСТЬ
  4. Эффективность социальной работы
  5. Эффективность
  6. Оценка эффективности нововведения.
  7. 1.3. Критерии эффективности фокусированного интервью
  8. Эффективность допроса
  9. Психологические условия эффективной требовательности.
  10. 1.3 КРИТЕРИИ ЭФФЕКТИВНОСТИ ФОКУСИРОВАННОГО ИНТЕРВЬЮ
  11. Статья 55. Лишение права занимать определенные должности или заниматься определенной деятельностью
  12. Эффективность отражения социальной действительности в журналистике
  13. Эффективность отражения социальной действительности в журналистике
  14. ЭФФЕКТИВНЫЕ ПРИЕМЫ ПРОДАЖИ ТОВАРОВ
  15. Функции и черты психологически эффективной требовательности.
  16. Критерии оценки эффективности деятельности социального работника