Изменения

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