Изменения

<tex>NPC \cap SPARCE SPARSE \ne \varnothing \Rightarrow P=NP</tex>.|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 NPC \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> — полином.<tex>S\in SPARSE</tex>. Следовательно <tex>\forall n |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином. Тогда <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>r</tex> — также полином.