Вообще говоря, если у вас есть класс сложности X , то класс co- X состоит из всех задач, которые являются дополнением к задачам в X .Например, класс NP (интуитивно) соответствует проблемам, в которых, если ответ на вопрос «да», то существует быстрый способ проверки этого ответа.Таким образом, класс co- NP состоит из проблем, при которых, если ответ «нет», существует быстрый способ проверки этого ответа.Проблема «вот булева формула; есть ли способ присвоить значения переменным, чтобы сделать ее истинной?»является каноническим примером проблемы в NP , потому что если ответ «да», вы можете легко убедить кого-то - просто покажите им, как установить каждую переменную, чтобы все это оценивалось как истинное.Проблема "вот булева формула; всегда ли она верна?"является каноническим примером проблемы в co- NP , потому что, если ответ «нет», вы можете быстро убедить кого-то в этом, просто показав ему переменное присваивание, в результате которого формула оценивается как ложное.
Класс co- P четко определен, но в основном никто не ссылается на него, потому что P = co- P .Интуитивно это объясняется тем, что класс P состоит из всех проблем, которые могут быть эффективно решены.В этом смысле, если у вас есть проблема R, чье дополнение может быть эффективно решено, тогда вы можете легко решить R - решить дополнение R, а затем перевернуть результат.Формально говоря, вы можете доказать это, показав, что любой решатель за полиномиальное время для языка в co- P может быть преобразован в решатель за полиномиальное время для языка в P (и наоборот), просто отрицая вывод этого решателя.