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

Лемма:

[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]