Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/accept-after-t-steps-in-npc — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) |
StasFomin (обсуждение | вклад) (тотальный сброс резервирования) |
| (не показана 1 промежуточная версия 1 участника) | |
(нет различий)
| |
Текущая версия на 12:58, 25 сентября 2025
Язык L состоит из пар (M, t), где
- M
- одноленточная машина Тьюринга над бинарным алфавитом.
- t
- число t единичной системе (t единиц).
- Существует вход x, M(x) останавливается и возвращает 1, после t шагов.
Покажите, что это NP-полная задача.