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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «Язык ''L'' состоит из пар (M, t), где ;M: одноленточная машина Тьюринга над бинарным алфавитом.…»)
(нет различий)

Версия 01:26, 17 марта 2022

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

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

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