Участник:Nikitashapovalov/ТеорУпражнения/Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/conp-as-yes

• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/conp-as-yes

---

Покажите, что язык L лежит в co-NP тогда и только тогда, если существует недетерминированная машина M, и полином p, такой, что M останавливается за время p(n) для всех входов x длины n, и L состоит точно только из таких строк x, у которых все пути вычисления M(x) приводят к ответу «1».

Задача зарезервирована: Nikitashapovalov 23:59, 19 декабря 2024 (UTC)

---

Условие

Покажите, что язык L лежит в co-NP тогда и только тогда, если существует недетерминированная машина M, и полином p, такой, что M останавливается за время p(n) для всех входов x длины n, и L состоит точно только из таких строк x, у которых все пути вычисления M(x) приводят к ответу «1».

Решение

StasFomin 00:39, 24 декабря 2024 (UTC): Стоп тут. Что значит «решает»? — для НМТ это очень неоднозначно, в отличие от МТ.

Вот хоть такое определение возьмите. Вам же будет проще.