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