CoNP

Материал из DISCOPAL
Версия от 09:55, 4 августа 2008; WikiSysop (обсуждение) (1 версия)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Класс-дополнение к классу NP.

Определение через детерминированную машину Тьюринга

Язык принадлежит классу coNP, если существует детерминированная машина Тьюринга M и некоторый полином p(*) такие, что


Диаграмма «ближайших» классов сложности

[svg]

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

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

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

Источник — «https://discopal.ispras.ru/index.php?title=CoNP&oldid=577»