WikiSort.ru - Не сортированное

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