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