109
правок
Изменения
→Иллюстрация
Осталось показать, что <tex>SAT \cap A</tex> не является NP-полным. Пусть
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <texmath>f</texmath>,
[[Сведение по Карпу|сводящая по Карпу]] <tex>SAT</tex> к <tex>SAT \cap A</tex>.
