Изменения

что если [[P]] не совпадает с [[NP]], то существует язык <mathtex>L</mathtex>,принадлежащий <mathtex>NP</mathtex>, но не являющийся полиномиальным и [[NP-полнота|NP-полным]].

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

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

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

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

Возьмём формулу <mathtex>\varphi</mathtex> длиной <mathtex>^{2k+1}10</mathtex>. Она не лежит в <mathtex>A</mathtex> и, следовательно, в <mathtex>SAT \cap A</mathtex>.Функция <mathtex>f</mathtex> не может перевести <mathtex>\varphi</mathtex> в промежуток<mathtex>\left[^{2k+2}10, ^{2k+4}10\right)</mathtex> или дальше, так как размер

входа. Значит, <mathtex>\varphi</mathtex> отображается в меньший промежуток, но

к этому то, что проверку на принадлежность <mathtex>f(\varphi)</mathtex> к<mathtex>SAT \cap A</mathtex> можно осуществить за <mathtex>O(2^{poly})</mathtex>(это следует из её принадлежности классу <mathtex>NP</mathtex>), получаем программу,разрешающую <mathtex>\varphi</mathtex> за полином. Утверждение о том, что все формулы<mathtex>\varphi</mathtex> длиной <mathtex>^{2k+1}10</mathtex> принадлежат классу<mathtex>P</mathtex>, скорее всего не верно, и, следовательно, язык <mathtex>SAT \cap A</mathtex> не является NP-полным.

Будем искать язык <mathtex>A</mathtex>, удовлетворяющий следующим условиям:#<mathtex>A \in P</mathtex> (что влечёт за собой<mathtex>SAT \cap A \in NP</mathtex>);#<mathtex>SAT \cap A \not\in P</mathtex>;#<mathtex>SAT \nleqslant not \leq SAT \cap A</mathtex>.

Если такой язык существует, то <mathtex>L = SAT \cap A</mathtex> является искомым примером множестваиз <mathtex>NP \setminus (P \cup NPC)</mathtex>.

Можно перечислить (возможно, с повторениями) все языки из <mathtex>P</mathtex>.

<mathtex> \tilde{p_0}, \tilde{p_1}, \ldots, \tilde{p_n}, \ldots</mathtex>Обозначим за <mathtex>p_i</mathtex> программу, запускающую <mathtex>\tilde{p_i}</mathtex>с таймером <mathtex>in^i</mathtex>. Тогда среди <mathtex>{p_i}</mathtex> встречаютсятолько программы из <mathtex>P</mathtex>, и для каждой полиномиальной программы<mathtex>\tilde{p_i}</mathtex>, работающей за полином <mathtex>g_i(n)</mathtex>, существуетномер <mathtex>j</mathtex> такой, что <mathtex>jn^j > g_i(n)</mathtex> для всех натуральных <mathtex>n</mathtex>и <mathtex>\tilde{p_j}</mathtex> делает то же самое, что и <mathtex>\tilde{p_i}</mathtex>.Таким образом, <mathtex>p_j</mathtex> распознает тот же язык, что и <mathtex>\tilde{p_i}</mathtex>.

Можно перечислить все функции из <mathtex>\tilde{P}</mathtex>.

Аналогично предыдущему доказательству, сначала построим последовательность <mathtex>\tilde{f_i}</mathtex>, а затем, добавив таймер <mathtex>in^i</mathtex>, получим последовательность <mathtex>f_i</mathtex>.

===Описание способа построения <mathtex>A</mathtex>===Упорядочим все слова по возрастанию длины. Разобьем всё <mathtex>\Sigma^{*}</mathtex> на множества<mathtex>A_i</mathtex> так, что <mathtex>\forall i<j, \forall \alpha \in A_i, \beta \in A_j: |\alpha| < |\beta|</mathtex>(то есть разбиение происходит по длинам, причем <mathtex>A_i</mathtex> идут «подряд»),<mathtex>SAT \cap \bigcup_{i=0}^{k} A_{2i}</mathtex> отличается от <mathtex>L(p_k)</mathtex> элементомиз <mathtex>\bigcup_{i=0}^{2k} A_i</mathtex> и для любого <mathtex>k</mathtex> существует <mathtex>\alpha \in \bigcup_{i=0}^{2k+1} A_i</mathtex>,для которого выполняются условия <mathtex>f_k(\alpha) \in \bigcup_{i=0}^{2k+1} A_i</mathtex> и <mathtex>[\alpha \in SAT] \ne [f_k(\alpha) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]</mathtex>.

Если мы сможем построить такие <mathtex>A_i</mathtex>, то язык <mathtex>L = SAT \cap \bigcup_{i=0}^{\infty} A_{2i}</mathtex>

<mathtex>SAT</mathtex> к <mathtex>L</mathtex>.

Попытаемся построить такую полиномиальную функцию <mathtex>f</mathtex>, что <mathtex>A_i = \left\{x \mid f(|x|) = i\right\}</mathtex>. Тогда

===Построение <mathtex>f</mathtex>===Зададим <mathtex>f(0) = f(1) = 0</mathtex>. Затем рекурсивно определим <mathtex>f(n)</mathtex>. Для этого рассмотрим три случая:*<mathtex>(\log_2 n) ^ {f(n-1)} \ge n</mathtex>:*:<mathtex>f(n) = f(n-1)</mathtex>;*<mathtex>f(n-1)=2i</mathtex>:*:если существует <mathtex>x</mathtex> такой, что <mathtex>|x| < \log_2 n</mathtex> и <mathtex>p_i(x) \ne L(x)</mathtex>, то <mathtex>f(n) = f(n-1)+1</mathtex>, иначе <mathtex>f(n) = f(n-1)</mathtex>;*<mathtex>f(n-1)=2i+1</mathtex>:*:если существует <mathtex>x</mathtex> такой, что <mathtex>|x| < \log_2 n</mathtex>,<mathtex>|f_i(x)| < \log_2 n</mathtex> и <mathtex>SAT(x) \ne L(f_i(x))</mathtex>, то <mathtex>f(n) = f(n-1)+1</mathtex>, иначе <mathtex>f(n) = f(n-1)</mathtex>.

Заметим, что вызовы <mathtex>L(\alpha)</mathtex> делаются для <mathtex>\alpha</mathtex>, для которых <mathtex>f</mathtex> уже построена.

Первый случай позволяет сказать, что <mathtex>f(n)</mathtex> ограничена <mathtex>O\left(\log_{\log_2 n} n\right) = O(\log_2 n)</mathtex>.Второй «ответственен» за множества <mathtex>A_i</mathtex> для чётных <mathtex>i</mathtex>, третий — для нечетных.Логарифм в условии <mathtex>|x| < \log_2 n</mathtex> необходим для полиномиальности <mathtex>f(n)</mathtex>.

===Полиномиальность <mathtex>f</mathtex>===Покажем, что <mathtex>f \in \tilde{P}</mathtex>. Для упрощения будем считать, что алфавит <mathtex>\Sigma=\{0,1\}</mathtex>.

<mathtex>T(n) = T(n-1) + a(n)(b_1(n) + b_2(n) + b_3(n) + b_4(n)) + c_1(n) + c2_2(n)</mathtex>, где:*<mathtex>T(n-1)</mathtex> идёт на вычисление <mathtex>f(n-1)</mathtex>;*<mathtex>a(n)</mathtex> — время перебора всех слов <mathtex>x</mathtex> таких, что <mathtex>|x| < \log_2 n</mathtex>;*<mathtex>b_1(n)</mathtex> — время работы <mathtex>p_i(x)</mathtex>;*<mathtex>b_2(n)</mathtex> — время работы <mathtex>SAT(x)</mathtex>;*<mathtex>b_3(n)</mathtex> — время работы <mathtex>L(x)</mathtex>;*<mathtex>b_4(n)</mathtex> — время работы <mathtex>L(f_i(x))</mathtex>;*<mathtex>c_1(n)</mathtex> — время, необходимое для построения программы <mathtex>p_i</mathtex>;*<mathtex>c_2(n)</mathtex> — время, необходимое для построения функции <mathtex>f_i</mathtex>.

<mathtex>a(n) = O\left(2^{\log_2 n}\right) = O(n)</mathtex>, таким образом <mathtex>a(n) \in \tilde{P}</mathtex>.

<mathtex>b_1(n) = O\left(i(\log_2 n)^i\right) = O\left(f(n-1)(\log_2 n)^{f(n-1)}\right) = O\left(f(n-1)n\right) = O(n^2) \in \tilde{P}</mathtex>

<mathtex>b_2(n) = O \left( 2^{\log_2 n} \log_2 n\right) = O\left(n \log_2 n\right) = O\left(n^2\right) \in \tilde{P}</mathtex>

<mathtex>b_3(n) = O \left(2^{\log_2 n} \log_2 n + \log_2 n\right) = O \left(n \log_2 n\right) = O\left(n^2\right) \in \tilde{P}</mathtex>

<mathtex>b_4(n) = b_3(b_1(n)) = O\left(n^4\right) \in \tilde{P}</mathtex>

Чтобы построить программу <mathtex>p_i</mathtex> достаточно построить <mathtex>\tilde{p_i}</mathtex>. Из того, что все <mathtex>\tilde{p_i}</mathtex> упорядочены по длине, следует, что длина<mathtex>\tilde{p_i}</mathtex> не превосходит <mathtex>ci</mathtex> (константа зависит от языка описания программы).Поэтому для построения i-ой программы достаточно перебрать все <mathtex>2^{ci+1}-1</mathtex> слов с длиной не больше <mathtex>ci</mathtex>и вывести i-ое, являющееся программой. Такой способ требует <mathtex>O(2^{ci}i) = O(2^{\log_2 n} \log_2 n) = O(n^2)</mathtex> времени.Аналогично можно построить и <mathtex>f_i</mathtex>. Из этого следует, что <mathtex>c_1(n)</mathtex> и <mathtex>c_2(n)</mathtex> тоже полиномиальны.

Получаем, что <mathtex>T(n) = T(n-1) + poly</mathtex>. Значит, <mathtex>T(n) \le n \cdot poly </mathtex>. Поэтому <mathtex>T(n) \in \tilde{P}</mathtex> и <mathtex>A \in P</mathtex>.

Таким образом, <mathtex>f</mathtex> полиномиальна и <mathtex>A \in P</mathtex>.

===Доказательство выполнения свойств <mathtex>A</mathtex>===Предположим, что <mathtex>\lim_{n \to \infty}f(n) = 2i</mathtex>. Это значит, что фунция «застряла» в ветке «иначе» случая два,но из этого следует, что <mathtex>SAT</mathtex> не отличается от <mathtex>L(p_i)</mathtex>. Этовлечёт за собой принадлежность <mathtex>SAT</mathtex> к <mathtex>P</mathtex>, что противоречит предположению <mathtex>P \ne NP</mathtex>.

Аналогично, в случае, если <mathtex>\lim_{n \to \infty}f(n) = 2i+1</mathtex>. Тогда функция «застряла» в ветке «иначе» случая три.Следствием этого является то, что <mathtex>SAT</mathtex> функцией <mathtex>p_i</mathtex> сводится к конечному множеству, что тожепротиворечит предположению <mathtex>P \ne NP</mathtex>.

Получается, что <mathtex>\lim_{n \to \infty}f(n) = +\infty</mathtex>, но по построению если <mathtex>f</mathtex> неограниченно растет,то <mathtex>L</mathtex> не совпадает ни с каким языком <mathtex>L(p_i)</mathtex> и ни одна функция <mathtex>f_i</mathtex> не сводит<mathtex>SAT</mathtex> к <mathtex>L</mathtex>. Следовательно, выполняются все три требуемых свойста, и <mathtex>L</mathtex> является примеромязыка из <mathtex>NP\setminus(P \cup NPC)</mathtex>.