Изменения
Нет описания правки
|statement=<tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
|proof=
#Очевидно, что <tex>\mathrm{LSAT} \in \mathrm{NP}</tex> (в качестве [[Классы NP, coNP, Σ₁, Π₁|сертификата ]] можно запросить <tex>x</tex>).
#[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи | Сведём]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{LSAT}</tex>. Для этого рассмотрим отображение <tex>\varphi \mapsto \langle \varphi, 1^{|\varphi|}\rangle</tex>, где <tex>|\varphi|</tex> — количество различных переменных в формуле <tex>\varphi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.
#*Если <tex>\varphi \in \mathrm{SAT}</tex>, то формула <tex>\varphi</tex> удовлетворима, а значит <tex>\exists x: x \leqslant_{lex} 1^{|\varphi|}, \varphi(x)=1</tex>. Такой <tex> x </tex> cуществует, потому что формула удовлетворима и любой вектор длины <tex> |\varphi| </tex> меньше либо равен единичному, значит мы переберем всевозможые вектора. Следовательно, <tex>\langle \varphi, 1^{|\varphi|}\rangle \in \mathrm{LSAT}</tex>.
#*Если <tex>\langle \varphi, 1^{|\varphi|}\rangle \in \mathrm{LSAT}</tex>, то <tex>\exists x: x \leqslant_{lex} 1^{|\varphi|}, \varphi(x)=1</tex>. Значит формула <tex>\varphi</tex> удовлетворима, и <tex>\varphi \in \mathrm{SAT}</tex>.
:Таким образом, <tex>\mathrm{SAT} \leqslant \mathrm{LSAT}</tex>. Но [[Теорема Кука | по теореме Кука ]]<tex>\mathrm{SAT} \in \mathrm{NPC}</tex>, а значит для любого <tex>L \in \mathrm{NP} </tex> выполнено <tex> L \leqslant \mathrm{SAT}</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP} \; L \leqslant \mathrm{LSAT}</tex>, то есть <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex>.
Они называются редкими потому, что строк длины <tex> n </tex> всего <tex> 2^{n} </tex>, и если язык содержит только полином от этого числа, то при большом <tex> n </tex> эта часть стремится к нулю.
'''Пример:''' Согласно [https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis тезису Чёрча - Тьюринга], существует биекция между машинами Тьюринга и программами. Зафиксировав язык, можно занумеровать программы, а следовательно и машины Тьюринга. <tex> \{1^{n} \mid n</tex>-я [[Машина Тьюринга | машина Тьюринга]] останавливается на в допускающем состоянии <tex> Y \} \in \mathrm{SPARSE}</tex>. Более того, любой унарный язык принадлежит <tex>\mathrm{SPARSE} </tex> (просто принять <tex> p(n) = 1 </tex>).
==Теорема==
