В теории алгоритмов часто рассматривается класс , тесно связанный с P и NP , — класс дополнений языков из NP , называемый co-NP .

Формальное определение

Класс сложности co-NP определяется для множества языков, то есть множеств слов над конечным алфавитом ${\displaystyle \Sigma }$ . Язык ${\displaystyle L\subseteq \Sigma ^{*}}$ принадлежит классу co-NP, если существует детерминированная машина Тьюринга M и некоторый полином p такие, что ${\displaystyle L=\{x\in \Sigma ^{*}:\forall y,|y|<p(|x|)M(x,y)=0\}}$ .

Отношения класса NP с другими классами

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М. : , 2006. — 1296 с. — ISBN 0-07-013151-1 .
• Джон Хопкрофт , Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М. : , 2002. — 528 с. — ISBN 0-201-44124-1 .

Это заготовка статьи по математике . Помогите Википедии, дополнив её.

В статье не хватает ссылок на источники (см. рекомендации по поиску ). Информация должна быть проверяема , иначе она может быть удалена. Вы можете статью, добавив ссылки на авторитетные источники в виде сносок . ( 8 марта 2017 )