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