Теорема Махэни — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 9: Строка 9:
  
 
{{Лемма
 
{{Лемма
|statement=<tex>\langle\phi,y\rangle \in LSAT, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in LSAT.</tex>
+
|statement=<tex>\langle\phi,y\rangle \in LSAT, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in LSAT</tex>.
 
}}
 
}}
  

Версия 00:35, 2 апреля 2012

Определение:
[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]NPC \cap SPARCE \ne \varnothing \Rightarrow P=NP[/math].