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