70
правок
Изменения
Новая страница: «{{Лемма |statement=<tex>L \in coNPC \Leftrightarrow \overline L \in NPC</tex> |proof= }} {{Определение |definition= <tex>SPARSE = \{L | \exists</...»
{{Лемма
|statement=<tex>L \in coNPC \Leftrightarrow \overline L \in NPC</tex>
|proof=
}}
{{Определение
|definition=
<tex>SPARSE = \{L | \exists</tex> полином <tex>p: \forall n \, |L \cap \Sigma^n| \le p(n)\}</tex>.
}}
{{Теорема
|author=Махэни
|about=light
|statement=<tex>coNPC \cap SPARSE = \varnothing \Rightarrow P = NP</tex>
|proof=
}}
|statement=<tex>L \in coNPC \Leftrightarrow \overline L \in NPC</tex>
|proof=
}}
{{Определение
|definition=
<tex>SPARSE = \{L | \exists</tex> полином <tex>p: \forall n \, |L \cap \Sigma^n| \le p(n)\}</tex>.
}}
{{Теорема
|author=Махэни
|about=light
|statement=<tex>coNPC \cap SPARSE = \varnothing \Rightarrow P = NP</tex>
|proof=
}}
