Изменения
Нет описания правки
{{Определение
|definition=
<tex>\mathrm{LSAT} = \{\langle \phi, y \rangle \mid \exists x: x \leqslant_{lex} y, \phi(x) = 1\}</tex>, где <tex> \phi </tex> {{---}} булева формула из <tex>n</tex> переменных, <tex>x, y \in \{0,1\}^{n} </tex> и отношение <tex> \leqslant_{lex} </tex> задает [[Лексикографический порядок | лексикографический порядок]].
}}
|proof=
#Очевидно, что <tex>\mathrm{LSAT} \in \mathrm{NP}</tex> (в качестве сертификата можно запросить <tex>x</tex>).
#[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи | Сведём ]] <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 \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>.
}}
{{Определение
|definition=
<tex>\mathrm{SPARSE}=\{L \mid \exists</tex> полином <tex> p: \forall n \, |L \cap \Sigma^n| \leqslant p(n)\}</tex>{{---}} множество редких (англ. ''sparse'') языков.
}}
То есть множество языков таких, что множество слов длины <tex> n </tex> из языка ограничено полиномом от <tex> n </tex>.
'''Пример:''' <tex> \{1^{n} \mid n</tex>-я [[Машина Тьюринга | машина Тьюринга ]] останавливается на <tex> Y \} \in \mathrm{SPARSE}</tex>. Более того, любой [https://en.wikipedia.org/wiki/Unary_language унарный язык ] принадлежит <tex>\mathrm{SPARSE} </tex> (просто принять <tex> p(n) = 1 </tex>).
{{Теорема
== Источники информации ==
* [http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html Блог Computational Complexity]
* [https://en.wikipedia.org/wiki/Sparse_language Sparse language]
[[Категория: Теория сложности]]
