Материал из Викиконспекты
| Лемма (1): |
[math]L \in coNPC \Leftrightarrow \overline L \in NPC[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]L \in coNPC[/math]. Тогда [math]L \in coNP[/math] и [math]\overline L \in NP[/math].
Рассмотрим произвольный язык [math]L_1 \in NP[/math]. Тогда [math]\overline {L_1} \in coNP[/math]. Так как [math]L \in coNPC[/math], то [math]\overline {L_1} \le_f L[/math], следовательно [math]L_1 \le_f \overline L[/math].
Получили, что [math]\overline L \in NP[/math] и [math]\forall L_1 \in NP \, L_1 \le_f \overline L[/math]. Значит [math]\overline L \in NPC[/math].
В обратную сторону доказательство аналогично. |
| [math]\triangleleft[/math] |
| Определение: |
| [math]TAUT = \{\phi | \forall x \, \phi(x)=1\}[/math]. |
| Лемма (2): |
[math]TAUT \in coNPC[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]\overline {TAUT} = \{\phi | \exists x : \phi(x) \ne 1\} = \{\phi | \overline {\phi} \in SAT\}[/math], то есть [math]\overline {TAUT} \in NPC[/math]. Тогда по лемме 1 [math]TAUT \in coNPC[/math]. |
| [math]\triangleleft[/math] |
| Определение: |
| [math]SPARSE = \{L | \exists[/math] полином [math]p: \forall n \, |L \cap \Sigma^n| \le p(n)\}[/math]. |
| Теорема (Махэни, light): |
[math]coNPC \cap SPARSE = \varnothing \Rightarrow P = NP[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть существует [math]S \in coNPC \cap SPARSE[/math]. Решим [math]TAUT[/math] за полином.
[math]check(\phi, i)[/math]
if [math]\phi=0[/math]
return 0
if [math]\phi=1[/math]
return 1
[math]memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, check(\phi|_{x_i=1}, i+1)[/math]
return [math]memo[\phi][/math]
blablabla
[math]check(\phi, i)[/math]
if [math]memo[f(\phi)] \ne -1[/math]
return [math]memo[f(\phi)][/math]
if [math]\phi=0[/math]
return 0
if [math]\phi=1[/math]
return 1
[math]memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, check(\phi|_{x_i=1}, i+1)[/math]
if [math]memo.size() \gt r(n)[/math]
exit [math]0[/math]
return [math]memo[f(\phi)][/math]
blablabla |
| [math]\triangleleft[/math] |
