Изменения

#Сведём <tex>SAT</tex> к <tex>LSAT</tex>. Для этого рассмотрим отображение <tex>\phi \mapsto \langle \phi, 1^m{|\phi|}\rangle</tex>, где <tex>m|\phi|</tex> — количество различных переменных в формуле <tex>\phi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное. #*Если <tex>\phi \in SAT</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x \le_{lex} 1^m{|\phi|}, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^m{|\phi|}\rangle \in LSAT</tex>.#*Если <tex>\langle \phi, 1^m{|\phi|}\rangle \in LSAT</tex>, то <tex>\exists x: x \le_{lex} 1^m{|\phi|}, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in SAT</tex>.