70
правок
Изменения
Нет описания правки
Итого, данная программа разрешает <tex>TAUT</tex> за полиномиальное время. А так как <tex>TAUT \in \mathrm{coNPC}</tex>, то <tex>\mathrm{P}=\mathrm{coNP}</tex>, то есть <tex>\mathrm{coP}=\mathrm{coNP}</tex>, откуда <tex>\mathrm{P}=\mathrm{NP}</tex>.
}}
== См. также ==
*[[Класс P]]
*[[Недетерминированные вычисления. Классы NP и Σ₁]]
[[Категория: Теория сложности]]
