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

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

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

Лемма:

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

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

[math]\triangleright[/math]

Очевидно, что [math]LSAT \in NP[/math]. Сведём [math]SAT[/math] к [math]LSAT[/math]. Для этого рассмотрим отображение [math]\phi \mapsto \langle \phi, 1^m\rangle[/math], где [math]m[/math] — количество различных аргументов в формуле [math]\phi[/math]. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное. Если [math]\phi \in SAT[/math], то формула [math]\phi[/math] удовлетворима, а значит [math]\exists x: x \lt _{lex} 1^m, \phi(x)=1[/math]. Следовательно, [math]\langle \phi, 1^m\rangle \in LSAT[/math]. Если [math]\langle \phi, 1^m\rangle \in LSAT[/math], то [math]\exists x: x \lt _{lex} 1^m, \phi(x)=1[/math]. Значит формула [math]\phi[/math] удовлетворима, и [math]\phi \in SAT[/math]. Таким образом, [math]SAT \le LSAT[/math]. Но [math]SAT \in NPC[/math], а значит [math]\forall L \in NP \; L \le SAT[/math]. Тогда в силу транзитивности [math]\forall L \in NP \; L \le LSAT[/math], то есть [math]LSAT \in NPH[/math]. Итого мы доказали, что [math]LSAT \in NPH[/math] и [math]LSAT \in NP[/math]. Тогда по определению [math]LSAT \in NPC[/math].

[math]\triangleleft[/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[/math]. Тогда [math]\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].