Класс co-NP

В теории алгоритмов часто рассматривается класс, тесно связанный с 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 с другими классами[править | править код]

Этот раздел статьи ещё не написан. Здесь может располагаться отдельный раздел. Помогите Википедии, написав его. (31 декабря 2013)

Литература[править | править код]

• Томас Х. Кормен и др. Алгоритмы: построение и анализ = 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)