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