Теорема Бермана — Форчуна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
 +
|about=1
 
|statement=<tex>L \in coNPC \Leftrightarrow \overline L \in NPC</tex>
 
|statement=<tex>L \in coNPC \Leftrightarrow \overline L \in NPC</tex>
 
|proof=Пусть <tex>L \in coNPC</tex>. Тогда <tex>L \in coNP</tex> и <tex>\overline L \in NP</tex>.
 
|proof=Пусть <tex>L \in coNPC</tex>. Тогда <tex>L \in coNP</tex> и <tex>\overline L \in NP</tex>.
Строка 8: Строка 9:
 
В обратную сторону доказательство аналогично.
 
В обратную сторону доказательство аналогично.
 
}}
 
}}
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
<tex>TAUT = \{\phi | \forall x \, \phi(x)=1\}</tex>.
 
<tex>TAUT = \{\phi | \forall x \, \phi(x)=1\}</tex>.
 
}}
 
}}
 +
 +
{{Лемма
 +
|about=2
 +
|statement=<tex>TAUT \in coNPC</tex>
 +
|proof=<tex>\overline {TAUT} = \{\phi | \exists x : \phi(x) \ne 1\} = \{\phi | \overline {\phi} \in SAT\}</tex>, то есть <tex>\overline {TAUT} \in NPC</tex>. Тогда по лемме 1 <tex>TAUT \in coNPC</tex>.
 +
}}
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=

Версия 14:43, 13 апреля 2012

Лемма (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]