109
правок
Изменения
м
→Иллюстрация: \phi -> \varphi
<math>\left[1,10^{10}\right),
\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> www как <math>^{n}a</math>.
Рассмотрим язык <math>SAT</math>. Логично предположить, что как в <math>A</math>,
к <math>SAT \cap A</math>.
Возьмем формулу <math>\phivarphi</math> длиной <math>^{2k+1}10</math>. Она не лежит в <math>A</math> и,следовательно, в <math>SAT \cap A</math>. Функция <math>f</math> не может перевести <math>\phivarphi</math>в промежуток <math>\left[^{2k+2}10, ^{2k+4}10\right)</math> или дальше, так как размер выходаполиномиальной функции не может быть экспоненциально больше длинны входа. Значит <math>\phivarphi</math>отображается в меньший промежуток, но в этом случае размер выхода экспоненциально меньше длины входа. Добавляя к этому то, что проверку на принадлежность <math>f(\phivarphi)</math> <math>SAT \cap A</math> можно осуществитьза <math>O(2^{poly})</math> (это следует из принадлежности <math>NP</math>), получаем программу разрешающую <math>\phivarphi</math> за полином, а это почему-то плохо.
==Доказательство==
