70
правок
Изменения
Нет описания правки
|author=Махэни
|about=light
|statement=<tex>coNPC \cap SPARSE = \ne \varnothing \Rightarrow P = NP</tex>
|proof=Пусть существует <tex>S \in coNPC \cap SPARSE</tex>. Разрешим <tex>TAUT</tex> за полином.
