Полиномиальное сведение
Чтобы точно выразить этот критерий, мы предположим, что задача X в нашей вычислительной модели может быть напрямую решена с полиномиальным вре- менем. Допустим, имеется некий «черный ящик», способный решать экземпляры задачи X; если передать ему входные данные для экземпляра X, то «черный ящик» за один шаг вернет правильный ответ. А теперь зададимся следующим вопросом:
(*) Возможно ли решить произвольный экземпляр задачи Y с полиномиальным количеством стандартных вычислительных шагов, дополняемых полиномиаль- ным количеством обращений к «черному ящику», решающему задачу X?
Если ответ на этот вопрос положителен, то мы используем запись Y
Источник:
Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016
Еще по теме Полиномиальное сведение:
- Статья 422. Разглашение сведений военного характера, составляющих государственную тайну, или потеря документов или материалов, содержащих такие сведения
- 16.3. Перечни сведений, составляющих государственную тайну, и сведения, которые не могут относиться к государственной тайне
- Статья 158. Фальсификация избирательных документов, документов референдума или фальсификация итогов голосования, предоставление ложных сведений в органов Государственного реестра избирателей или фальсификация сведений Государственного реестра избирателей
- 16.6. Рассекречивание сведений и их носителей
- 16.7. Распоряжение сведениями, составляющими государственную тайну
- Статья 895. Конфиденциальность сведений о договоре
- 16.4. Отнесение сведений к государственной тайне и их засекречивание
- Дополнительные сведения
- Дополнительные сведения
- I. Общие сведения о профессии.
- I. Общие сведения о профессии.
- 4.3. ПЛАНЕТЫ Общие сведения
- 4.4. Поля Общие сведения
- 4.5. АСПЕКТЫ Общие сведения
- 1. Краткие общие сведения
- 1. Краткие общие сведения
- § 3. Требование об опровержении порочащих сведений (п. 2516-2519)
- Знаки зодиака Общие сведения
- Некоторые полезные сведения об аспектах
-
Windows -
Архитектура компьютера -
Интернет -
Информатика -
Компьютер -
Компьютерные и телекоммуникационные системы -
Программирование -
Социальные сети -
-
Английский язык -
Астрология -
Астрономия -
Биология -
Военная литература -
Журналистика -
Компьютерная инженерия -
Педагогика -
Право -
Психология -
Социология -
Lecture.Center