NP-полные задачи

Не достигув прогресса в разрешении вопроса P = NP, ученые обратились к сопут- ствующему, но более доступному вопросу: какие задачи в NP обладают наибольшей сложностью? Сведение к полиномиальному времени позволяет нам рассмотреть этот вопрос и получить представление о структуре NP.

Возможно, самый естественный способ определения «наиболее сложной» за- дачи X основан на следующих двух свойствах: (i) X NP и (ii) для всех Y NP Y

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

Еще по теме NP-полные задачи:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.