Класс co-NP

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

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

Класс сложности co-NP определяется для множества языков, то есть множеств слов над конечным алфавитом . Язык принадлежит классу co-NP, если существует детерминированная машина Тьюринга M и некоторый полином p такие, что .

Отношения класса 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.