Бюрократы, editor, Администраторы
422
правки
Изменения
\bigm|
{{Определение
|definition=
<tex>\mathrm{LSAT}=\{\langle\phi,y\rangle \bigm| \exists x: x\le_{lex}y, \phi(x) = 1\}</tex>.
}}
<tex>S\in \mathrm{SPARSE}</tex>. Следовательно, <tex>\forall n \; |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином.
Тогда <tex>|\{x\in S\, bigm|\, |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>r</tex> — также полином.
Опишем алгоритм для нахождения лексикографически минимальной строки <tex>x</tex>, удовлетворяющей формулу <tex>\phi</tex>.
