Изменения
Нет описания правки
Так как <tex>S\in NPC</tex>, и <tex>LSAT \in NP</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \phi, y \rangle \in LSAT \iff f(\langle \phi, y \rangle) \in S</tex>.
Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi|=|y|</tex>(<tex>|y|</tex> — длина вектора <tex>y</tex>), то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.
<tex>S\in SPARSE</tex>. Следовательно, <tex>\forall n \; |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином.
