Изменения
Нет описания правки
|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 \le_{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 \le_{lex} 1^m, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in SAT</tex>.
