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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

M
одноленточная машина Тьюринга над бинарным алфавитом.
t
число t единичной системе (t единиц).
  • Существует вход x, M(x) останавливается и возвращает 1, после t шагов.

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

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

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

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