Изменения

Теорема Бермана — Форчуна

34 байта убрано, 23:55, 27 апреля 2012

Нет описания правки

{{Теорема

~~|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> за полином.

70

правок