Я видел несколько мест, которые просто заявили, что известно, что P является подмножеством пересечения NP и co-NP. Доказательства, показывающие, что P - подмножество NP, найти нелегко. Таким образом, чтобы показать, что это подмножество пересечения, все, что осталось сделать, показывает, что P является подмножеством co-NP. Что может быть доказательством этого? Большое вам спасибо!
Почему P ⊆ co-NP?
Ответ 1
Класс P закрыт при дополнении: если L - язык в P, то дополнение к L также находится в P. Вы можете увидеть это, взяв любой алгоритм решения многочленов для L и переключив состояния принятия и отклонения; эта новая машина теперь решает дополнение L и делает это в полиномиальное время.
Язык L находится в co NP, если его дополнение находится в NP. Поэтому рассмотрим любой язык L & in; P. Дополнение L также находится в P, поэтому дополнение L в этом случае находится в NP (поскольку P & subseteq; NP). Следовательно, L находится в co NP. Следовательно, P & subseteq; СО- NP.
Надеюсь, это поможет!
Ответ 2
Подумайте об этом так. Рассмотрим класс co-P. Так как P замкнуто относительно комплимента, P = co-P.
Также должно быть ясно, что co-P является подмножеством co-NP, потому что P содержится в NP. Так как P = co-P, то P содержится в co-NP.