Полиномиальное сведение

Мы намереваемся исследовать пространство вычислительно сложных задач, что- бы в конечном итоге прибыть к математической характеристике большого класса. Основным приемом в этом исследовании будет сравнение относительной слож- ности разных задач; нам хотелось бы найти формальное выражение для таких утверждений, как «задача X обладает как минимум не меньшей сложностью, чем задача Y».
Для формализации будет применен метод сведения: чтобы показать, что некоторая задача X по меньшей мере не менее сложна, чем другая задача Y, мы докажем, что «черный ящик», способный решить задачу X, также сможет решить задачу Y. (Другими словами, решение X будет достаточно мощным для того, чтобы также решить Y.)

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

(*) Возможно ли решить произвольный экземпляр задачи Y с полиномиальным количеством стандартных вычислительных шагов, дополняемых полиномиаль- ным количеством обращений к «черному ящику», решающему задачу X?

Если ответ на этот вопрос положителен, то мы используем запись Y

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

Еще по теме Полиномиальное сведение:

  1. Статья 422. Разглашение сведений военного характера, составляющих государственную тайну, или потеря документов или материалов, содержащих такие сведения
  2. 16.3. Перечни сведений, составляющих государственную тайну, и сведения, которые не могут относиться к государственной тайне
  3. Статья 158. Фальсификация избирательных документов, документов референдума или фальсификация итогов голосования, предоставление ложных сведений в органов Государственного реестра избирателей или фальсификация сведений Государственного реестра избирателей
  4. 16.6. Рассекречивание сведений и их носителей
  5. 16.7. Распоряжение сведениями, составляющими государственную тайну
  6. Статья 895. Конфиденциальность сведений о договоре
  7. 16.4. Отнесение сведений к государственной тайне и их засекречивание
  8. ИНЖЕНЕР ВСПОМИНАЕТ НУЖНЫЕ СВЕДЕНИЯ
  9. Дополнительные сведения
  10. Дополнительные сведения
  11. I. Общие сведения о профессии.
  12. I. Общие сведения о профессии.
  13. 4.3. ПЛАНЕТЫ Общие сведения
  14. 4.4. Поля Общие сведения
  15. 4.5. АСПЕКТЫ Общие сведения
  16. 1. Краткие общие сведения
  17. 1. Краткие общие сведения
  18. § 3. Требование об опровержении порочащих сведений (п. 2516-2519)
  19. Знаки зодиака Общие сведения