Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/accept-after-t-steps-in-npc

Ссылки сюда (2) →

Задача зарезервирована: Ydanyok 09:10, 13 декабря 2024 (UTC)

Язык L состоит из пар (M, t), где

M

одноленточная машина Тьюринга над бинарным алфавитом.

t

число t единичной системе (t единиц).

• Существует вход x, M(x) останавливается и возвращает 1, после t шагов.

Покажите, что это NP-полная задача.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.