Изменения
Нет описания правки
{{Определение
|definition=
<tex>\mathrm{LSAT} = \{\langle \phi, y \rangle \mid \exists x: x \leqslant_{lex} y, \phi(x) = 1\}</tex>, где <tex> \phi </tex> {{---}} булева формула, и из <tex> x \leqslant_{lex} y n</tex> означаетпеременных, что вектор <tex> x , y \in \{0,1\}^{n} </tex> лексикографически меньше или равен вектору и отношение <tex> y \leqslant_{lex} </tex>задает лексикографический порядок.
}}
#*Если <tex>\phi \in \mathrm{SAT}</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x \leqslant_{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 \leqslant_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in \mathrm{SAT}</tex>.
:Таким образом, <tex>\mathrm{SAT} \leqslant \mathrm{LSAT}</tex>. Но [[Теорема Кука | <tex>\mathrm{SAT} \in \mathrm{NPC}</tex>]], а значит <tex>\forall L \in \mathrm{NP} \; L \leqslant \mathrm{SAT}</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP} \; L \leqslant \mathrm{LSAT}</tex>, то есть <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex>.
Итого мы доказали, что <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex> и <tex>\mathrm{LSAT} \in \mathrm{NP}</tex>. Тогда по определению <tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
}}
<tex>\mathrm{SPARSE}=\{L \mid \exists</tex> полином <tex> p: \forall n \, |L \cap \Sigma^n| \leqslant p(n)\}</tex>
}}
То есть множество языковтаких, таких что множество слов длины <tex> n </tex> из языка ограничено полиномом от <tex> n </tex>.
'''Пример:''' <tex> \{1^{n} \mid n</tex>-я машина Тьюринга останавливается на <tex> Y \} \in \mathrm{SPARSE}</tex>. Более того, любой унарный язык принадлежит <tex>\mathrm{SPARSE} </tex> (просто принять <tex> p(n) = 1 </tex>).
