70
правок
Изменения
Нет описания правки
|about=light
|statement=<tex>coNPC \cap SPARSE = \varnothing \Rightarrow P = NP</tex>
|proof=Пусть существует <tex>S \in coNPC \cap SPARSE</tex>. Решим <tex>TAUT</tex> за полином. <tex>check(\phi, i)</tex> '''if''' <tex>(memo[\phi] \ne -1)</tex> '''return''' <tex>memo[\phi]</tex> '''if''' <tex>\phi=0</tex> '''return''' 0 '''if''' <tex>\phi=1</tex> '''return''' 1 <tex>memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, check(\phi|_{x_i=1}, i+1)</tex> blablabla
}}
