Изменения

[[Сведение по Карпу|сводящая по Карпу]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{SAT} \cap A</tex>.

Она не лежит в <tex>A</tex> и, следовательно, в <tex>\mathrm{SAT} \cap A</tex>.

Функция <tex>f</tex> не может перевести <tex>\varphi</tex> в промежуток

выхода полиномиальной функции не может быть экспоненциально больше длины

входа. Значит, <tex>\varphi</tex> отображается в меньший промежуток, но

(это следует из её принадлежности классу <tex>\mathrm{NP}</tex>), получаем программу,

разрешающую <tex>\varphi</tex> за полином. Утверждение о том, что все формулы

<tex>\mathrm{P}</tex>, скорее всего не верно, и, следовательно, язык

<tex>\mathrm{SAT} \cap A</tex> не является NP-полным.