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