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