Теорема Бермана — Форчуна

Материал из Викиконспекты
Версия от 20:42, 9 апреля 2012; AndrewD (обсуждение | вклад) (Новая страница: «{{Лемма |statement=<tex>L \in coNPC \Leftrightarrow \overline L \in NPC</tex> |proof= }} {{Определение |definition= <tex>SPARSE = \{L | \exists</...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Лемма:
[math]L \in coNPC \Leftrightarrow \overline L \in NPC[/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]