109
правок
Изменения
→Иллюстрация: исправлена пара опечаток
==Иллюстрация==
Определим язык <math>A</math> как множество таких формул <math>\alpha</math>,
что <math>\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor</math> чётно.
Иными словами, <math>A</math> — это язык формул с длинами, лежащими в промежутках
Рассмотрим язык <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>.
