Доказательство NР-полноты других задач

Утверждение (8.13) открывает путь к более полному пониманию сложных задач в NP: получив первую NP-полную задачу, мы можем обнаружить много больше таких задач при помощи простого наблюдения.

(8.14) Если Y — NP-полная задача, а X — задача в NP, обладающая свойством

Y

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

Еще по теме Доказательство NР-полноты других задач:

  1. Полноте презирать тело, полноте шутить с ним!
  2. Cудебное следствие, т. е. разработка собранных по делу доказательств пред решающими судьями, основывается на трех началах, которые составляют коренные принципы теории доказательств, принявшей внутреннее убеждение мерилом достоверности.
  3. § 82 Доказательства вотчинного права. – Различие между доказательством и укреплением. – Можно ли утвердить вотчинное право по приобретению без укрепления. – Значение и сила неформальных актов
  4. Полнота и пустота
  5. Полнота и пустота
  6. § 55 Общие понятия о поклаже. – Поклажа свободная и необходи- мая, по русскому закону. – Кто может вступать в договор о поклаже. – Доказательство поклажи. – Сохранная расписка. – Когда не требуется письменное доказательство. – Обязанности приемщика. – Поклажа в запертом помещении. – Растрата. – Ответственность приемщика. – Возвращение поклажи при несостоятельности. – Вызов наследников приемщика и отдатчика. – Поклажа в гостиницах.
  7. Глава III - ПОЛНОТА
  8. Пустота и полнота
  9. Пустота и полнота
  10. Пустота и полнота