Теорема Махэни

Определение:

[math]LSAT=\{\langle\phi,y\rangle | \exists x: x\lt _{lex}y, \phi(x) = 1\}[/math].

Лемма:

[math]LSAT \in NPC[/math].

Лемма:

[math]\langle\phi,y\rangle \in LSAT, y\lt _{lex}z[/math]. Тогда [math]\langle\phi,z\rangle \in LSAT[/math].

Доказательство:

[math]\triangleright[/math]

[math]\langle\phi,y\rangle \in LSAT \Rightarrow \exists x: x\lt _{lex}y, \phi(x) = 1[/math]. Так как [math]y\lt _{lex}z[/math], то [math]\exists x: x\lt _{lex}z, \phi(x) = 1[/math], следовательно, [math]\langle\phi,z\rangle \in LSAT[/math].

[math]\triangleleft[/math]

Теорема (Махэни):

[math]NPC \cap SPARCE \ne \varnothing \Rightarrow P=NP[/math].