211
правок
Изменения
м
Нет описания правки
|author=Махэни
|statement=
<tex>\mathrm{NPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}</tex>.
|proof=Пусть <tex>S \in \mathrm{NPC} \cap \mathrm{SPARSE}</tex>.
== См. также ==
*[[Класс P]]
*[[Недетерминированные вычисления. Классы NP и Σ₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
