211
правок
Изменения
м
Нет описания правки
#Очевидно, что <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>.
:Таким образом, <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>.
