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