109
правок
Изменения
м
→Иллюстрация
Рассмотрим язык <math>SAT</math>. Логично предположить, что как в <math>A</math>,
так и в <math>\bar{A}</math> лежит бесконечное множество элементов из <math>SAT</math>,
не принадлежащих классу <math>P</math>распознаваемых за полиномиальное время, поэтому <math>SAT \cap A \not\in P</math>.
Из <math>A \in P</math> и <math>SAT \in NP</math> следует, что <math>SAT \cap A \in NP</math>.
