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

Текущая версия на 00:41, 24 декабря 2024 (просмотреть исходный код) StasFomin (обсуждение | вклад) ← Предыдущая правка	Текущая версия на 00:41, 24 декабря 2024 (просмотреть исходный код) StasFomin (обсуждение | вклад)
(нет различий)

---

Текущая версия на 00:41, 24 декабря 2024

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

---

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

---

Условие

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

Решение

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

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