Изменения

что <math>\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor</math> чётно. Иными словами,<math>A</math> — это язык формул с длинами, лежащими в промежутках

\left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4, \underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \dots</math>Далее будем обозначать <math>\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n</math> как <math>^{n}a</math>.

так и в <math>\bar{A}</math> лежит бесконечное множество элементов из <math>SAT</math>.,не принадлежащих классу <math>P</math>, поэтому <math>SAT \cap A \not\in P</math>

ПредположимОсталось показать, что <math>SAT \cap A</math> не является NP-полным.ПустьИз это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f </math>сводящая по Карпу <math>SAT</math> к <math>SAT \cap A</math>.

Возьмем формулу <math>\varphi</math> длиной <math>^{2k+1}10</math>. Она не лежит в <math>A</math> и,следовательно, в <math>SAT \cap A</math>. Функция <math>f</math> не может перевести <math>\varphi</math>в промежуток <math>\left[^{2k+2}10, ^{2k+4}10\right)</math> или дальше, так как размер выхода полиномиальной функции не может быть экспоненциально больше длинны входа. Значит <math>\varphi</math> отображается в меньший промежуток, но в этом случае размер выхода экспоненциально меньше длины входа. Добавляя к этому то, что проверку на принадлежность <math>f(\varphi)</math> <math>SAT \cap A</math> можно осуществить за <math>O(2^{poly})</math> (это следует из принадлежности <math>NP</math>), получаем программу разрешающую <math>\varphi</math> за полином.Утверждение о том, что все формулы<math>\varphi</math> длиной <math>^{2k+1}10</math> принадлежат классу<math>P</math> скорее всего не верно, а ,следовательно, язык <math>SAT \cap A</math> не является NP-полным. Заметим, что это объяснение не является доказательством!