211
правок
Изменения
м
Нет описания правки
|proof=Пусть <tex>S \in NPC \cap SPARSE</tex>.
Так как <tex>S\in NPC</tex>, и <tex>LSAT \in NP</tex>, то существует полиномиальная функция сведения <tex>f:LSAT \mapsto S</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>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.
