70
правок
Изменения
Нет описания правки
{{Лемма
|about=1
|statement=Язык <tex>L \in </tex> является <tex>\mathrm{coNPCcoNP} \Leftrightarrow </tex>-полным тогда и только тогда, когда <tex>\overline L \in </tex> является <tex>\mathrm{NPCNP}</tex>-полным.|proof=Пусть <tex>L \in </tex> {{---}} <tex>\mathrm{coNPCcoNP}</tex>-полный. Тогда <tex>L \in \mathrm{coNP}</tex> и <tex>\overline L \in \mathrm{NP}</tex>.
Рассмотрим произвольный язык <tex>L_1 \in \mathrm{NP}</tex>. Тогда <tex>\overline {L_1} \in \mathrm{coNP}</tex>. Так как <tex>L \in </tex> {{---}} <tex>\mathrm{coNPCcoNP}</tex>-полный, то <tex>\overline {L_1} \le L</tex>, следовательно <tex>L_1 \le \overline L</tex> (по [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Свойства сведения|лемме]]).
Получили, что <tex>\overline L \in \mathrm{NP}</tex> и <tex>\forall L_1 \in \mathrm{NP} \Rightarrow L_1 \le \overline L</tex>. Значит <tex>\overline L \in \mathrm{NPC}</tex>.
Для начала напишем программу, разрешающую <tex>\mathrm{TAUT}</tex>:
<tex>check(\phi, i)</tex>:
'''return''' 0
'''return''' 1
'''return''' <tex>memo[\phi]</tex>
Ответом будет <tex>check(\phi, 1)</tex>.
Оценим необходимый размер <tex>memo</tex>. Можно считать, что <tex>\mathrm{T}(f, \phi) \le q(n)</tex>, где <tex>n = |\phi|</tex>, а <tex>q</tex> {{---}} монотонно возрастающий полином. Тогда <tex>|f(\phi)| \le q(n)</tex>. Так как <tex>S \in \mathrm{SPARSE}</tex>, то <tex>|S \cap \Sigma^k| \le p(k)</tex>, где <tex>p</tex> {{---}} полином. Можно считать, что <tex>p</tex> монотонно возрастает. Тогда размер <tex>memo</tex> можно оценить сверху: <tex>memo.size() \le \sum\limits_{i=0}^{q(n)}p(i) \le (1+q(n)) \cdot p(q(n)) \le r(n)</tex>, где <tex>r(n)</tex> {{---}} полином.
<tex>check(\phi, i)</tex>:
'''if''' <tex>\phi=0</tex>
'''return''' 0
'''if''' <tex>\phi=1</tex>
'''return''' 1
'''if''' <tex>memo[f(\phi)] \ne -1</tex> //(1) '''return''' <tex>memo[f(\phi)]</tex> <tex>memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)</tex> //(2)
'''if''' <tex>memo.size() > r(n)</tex>
'''exit''' <tex>0</tex>
