Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
|proof=Пусть <tex>S \in \mathrm{NPC} \cap \mathrm{SPARSE}</tex>.
Так как <tex>S\in \mathrm{NPC}</tex>, и <tex>LSAT \in \mathrm{NP}</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \phi, y \rangle \in LSAT \iff Leftrightarrow 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> — полином.
