211
правок
Изменения
м
Нет описания правки
{{Определение|definition=<tex>LSAT=Формулировка\{\langle\phi,y\rangle | \exists x: x<_{lex}y, \phi(x) =1\}</tex>.}} {{Лемма|statement=<tex>LSAT \in NPC</tex>.}} {{Лемма|statement=<tex>\langle\phi,y\rangle \in LSAT, y<_{lex}z</tex>NP . Тогда <tex>\langle\le Lphi,~Lz\rangle \in Sparce LSAT.</tex>}} {{Теорема|author=Махэни|statement=<tex>NPC \cap SPARCE \ne \varnothing \Rightarrow P = NP</tex>.|proof=}}
