Изменения

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

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

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

Осталось показать, что <mathtex>\mathrm{SAT } \cap A</mathtex> не является NP-полным. Пусть

[[Сведение по Карпу|сводящая по Карпу ]] <mathtex>\mathrm{SAT}</mathtex> к <mathtex>\mathrm{SAT } \cap A</mathtex>.

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

==ДоказательствоТеорема == {{Теорема|author=Ладнер|statement=<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</tex>.|proof=Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что никакой <tex>\mathrm{NP}</tex>-полный язык (например, [[Примеры NP-полных_языков. Теорема_Кука#NP-полнота_2|SAT]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу]] к полиномиальному. Будем искать такой язык <mathtex>A</mathtex>, удовлетворяющий чтобы язык <tex>L = \mathrm{SAT} \cap A</tex> удовлетворял следующим условиям: #<mathtex>A L \in P\mathrm{NP}</mathtex> (что влечёт за собойдля этого достаточно, чтобы выполнялось <mathtex>SAT \cap A \in NP\mathrm{P}</mathtex>);#<mathtex>SAT \cap A L \not\in \mathrm{P}</mathtex>;#<mathtex>\mathrm{SAT } \not \le L</tex>. Если выполнены все три свойства, то <tex>L \in \mathrm{NP} \setminus (\mathrm{P} \cup \nleqslant SAT mathrm{NPC})</tex>. Пусть <tex>M_1, \ldots, M_n, \ldots</tex> — все машины Тьюринга из <tex>\tilde{\mathrm{P}}</tex> (возможно, с повторениями), расположенные в таком порядке, чтобы <tex>T(M_i, x) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>. Пусть <tex>f_1, \ldots, f_n, \ldots</tex> — аналогичное множество полиномиальных функций: <tex>T(f_i, x) \le |x|^i</tex> для любого <tex>x \in \cap ASigma^*</mathtex>.

Если такой язык существуетДля простоты будем считать, то что <mathtex>L |\Sigma| = A 2</tex>. Построим такую ''неубывающую'' функцию <tex>g \in \tilde{\cap SATmathrm{P}}</mathtex> является искомым примером множестваиз , что при <mathtex>NP A = \setminus {x \in \Sigma^*: g(P |x|) \equiv 0 \pmod{2} \cup NPC)}</tex> для <tex>L</mathtex>выполняются три перечисленных свойства.

===Утверждение 1Алгоритм построения g ===Можно перечислить (возможно, с повторениями) все языки из <math>P</math>.

Действительно, рассмотрим последовательность всех программ, упорядоченных по длине:Положим <mathtex> \tilde{p_0}, \tilde{p_1}, \ldots, \tilde{p_n}, \ldots</math>Обозначим за <math>p_ig(0) = g(1) = 1</math> программу, запускающую <math>\tilde{p_i}</math>с таймером <math>in^i</mathtex>. Тогда среди Для <math>{p_i}</math> встречаютсятолько программы из <math>P</math>, и для каждой полиномиальной программы<mathtex>n \tilde{p_i}ge 1</mathtex>, работающей за полином построим <mathtex>q_ig(n+ 1)</mathtex>, существуетномер рекурсивно — с помощью <mathtex>j</math> такойg(0), что <math>jn^j > g_ig(n1)</math> для всех натуральных <math>n</math>,и <math>\tilde{p_j}</math> делает то же самоеldots, что и <math>\tilde{p_i}</math>.Таким образом, <math>p_j</math> распознает тот же язык, что и <math>\tilde{p_i}g(n)</mathtex>.

===Утверждение 2===Можно перечислить все функции из * Если <mathtex>(\tildelog_2 n)^{Pg(n)}\ge n</mathtex>, то <tex>g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов.

Аналогично предыдущему доказательству, сначала построим последовательность * Пусть вычисленное значение <mathtex>\tilde{f_i}</math>,а затем, добавив таймер <math>in^g(n) = 2 i</mathtex>, получим последовательность . Определим <mathtex>f_ig(n+1)</mathtex>.следующим образом:

===Описание способа построения for <mathtex>Ax</mathtex>===Упорядочим все слова по возрастанию длины. Разобьем всё : <mathtex>|x| \le \Sigma^{*}log_2 n</mathtex> на множества if <mathtex>A_iM_i(x)</mathtex> так, что and <mathtex>\forall i<j, \forall \alpha \in A_i, \beta \in A_j: [g(|x|) \alpha| < |equiv 1 \beta|pmod{2}</mathtex>(то есть разбиение происходит по длинам, причем or <mathtex>A_ix \not \in \mathrm{SAT}]</mathtex> идут подряд), <mathtex>SAT \cap \bigcup_{ig(n+1) :=0}^{k} A_{2i}g(n)+1</mathtex> отличается от return if <mathtex>L! M_i(p_kx)</mathtex> элементомиз and <mathtex>[g(|x|) \bigcup_{i=equiv 0}^\pmod{2k2} A_i</math> и для любого <math>k</mathtex> существует and <mathtex>\alpha x \in \bigcup_mathrm{i=0SAT}^{2k+1} A_i]</mathtex>,для которого выполняются условия <mathtex>f_kg(\alphan+1) \in \bigcup_{i:=0}^{2kg(n)+1} A_i</mathtex> и return <mathtex>[\alpha \in SAT] \ne [f_kg(\alphan+1) \in SAT \cap \bigcup_{i:=0}^{k} A_{2i}]g(n)</mathtex>.

* Пусть вычисленное значение <!--Куда-то сюда неплохо было бы добавить картинку-tex>g(n) = 2 i -1</tex>. Определим <tex>g(n+1)</tex>следующим образом:

Если мы сможем построить такие for <mathtex>A_ix</mathtex>: <tex>|x| \le \log_2 n, то язык |f_i(x)| \le \log_2 n<math/tex>L = if <tex>x \in \mathrm{SAT }</tex> and <tex>[g(|f_i(x)|) \cap equiv 1 \bigcup_pmod{i2}</tex> or <tex>f_i(x) \not \in \mathrm{SAT}]</tex> <tex>g(n+1) :=g(n)+1</tex> return if <tex>x \not \in \mathrm{SAT}</tex> and <tex>[g(|f_i(x)|) \equiv 0\pmod{2}^{</tex> and <tex>f_i(x) \in \infty} A_mathrm{2iSAT}]</mathtex>будет отличаться от любого полиномиального языка, и ни одна полиномиальная функция не будет сводить <mathtex>SATg(n+1) := g(n)+1</mathtex> к return <mathtex>Lg(n+1) := g(n)</mathtex>.

Попытаемся построить такую полиномиальную функцию <math>f</math>, что <math>A_i = \left\{x \mid f(|x|) = i\right\}</math>. Тогда <math>A=\left\{x \mid f(|x|) \, \vdots \, 2 \right\}</math> и <math>LКорректность алгоритма ==SAT \cap A = \left\{\varphi \mid \varphi \in SAT \and f(|\varphi|)\, \vdots \, 2\right\}</math>

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

Первый случай позволяет сказать, что * Пусть <mathtex>fg(n)</mathtex> ограничена не имеет предела при <mathtex>O\left(\log_{\log_2 n} n\right) = O(to \log_2 n)infty</mathtex>.Второй «ответственен» за множества Значит, для любой <tex>M_i</tex> в <tex>L</tex> существует элемент, на котором <mathtex>A_iM_i</mathtex> «ошибается»; аналогично, для чётных любой полиномиальной функции <mathtex>if_i</mathtex>существует элемент, третий — для нечетных.Логарифм в условии на котором <mathtex>|x| f_i< /tex> неверно сводит <tex>\log_2 nmathrm{SAT}</mathtex> необходим для полиномиальности к <mathtex>f(n)L</mathtex>. Оба свойства выполнены.

* Пусть <tex>\lim\limits_{n \to \infty} g(n) ===Полиномиальность 2i + 1<math/tex>f. Тогда в нашем множестве полиномиальных функций существует <tex>f_i : \forall x \Rightarrow [x \in SAT] = [g(|f_i(x)|) \equiv 0 \pmod{2} \wedge f_i(x) \in \mathrm{SAT}]</mathtex>===Покажем. С одной стороны, что <mathtex>f \in \tildemathrm{PSAT}\le L</tex> с помощью <tex>f_i</mathtex>. Для упрощения будем считатьС другой стороны, из определения <tex>A</tex> выходит, что алфавит язык <tex>L</tex> конечен, значит <mathtex>L \Sigma=in \mathrm{0,1\P}</mathtex>. Снова получено противоречие с предположением.

<math>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)</math>Таким образом, где:*при верности предположения <mathtex>T(n-1)</math> идёт на вычисление <math>f(n-1)</math>;*<math>a(n)</math> — время перебора всех слов <math>x</math> таких, что <math>|x| < \log_2 n</math>;*<math>b_1(n)</math> — время работы <math>p_i(x)mathrm{P} \neq \mathrm{NP}</mathtex>;*второе и третье свойства <math>b_2(n)</math> — время работы <math>SAT(x)</math>;*<math>b_3(n)</math> — время работы <math>L(x)</math>;*<math>b_4(n)</math> — время работы <mathtex>L(f_i(x))</math>;*<math>c_1(n)</math> — время, необходимое для построения программы <math>p_i</math>;*<math>c_2(n)</math> — время, необходимое для построения функции <math>f_i</mathtex>выполнены.

<math>a(n) = O\left(2^{\log_2 n}\right) = O(n)</math>, таким образом <math>a(n) \in \tilde{P}</math>.= Время работы алгоритма ===

Проверим выполнение первого свойства языка <mathtex>b_1L</tex>. Для этого достаточно установить полиномиальность <tex>A</tex>. Покажем, что <tex>T(g, n) = O\left</tex> отличается от <tex>T(g, n - 1)</tex> не более, чем на неубывающий полином <tex>p(i(\log_2 n)^i\right) = O\left(f</tex>. Из этого будет следовать полиномиальность <tex>g</tex>: <tex>T(g, n-1)\le p(\log_2 n)^{f+ p(n-1)}+ \rightldots + p(1) = O\left(fle n p(n-1)n\right) = Oin poly(n^2) \in \tilde{P}</mathtex>.

Заметим, что <mathtex>b_2g(n) = O \left( 2^{\log_2 le n} \log_2 </tex> по построению для <tex>n\right) = O\left(n \log_2 n\right) = O\left(n^2\right) \in \tilde{P}ge 1</mathtex>.

Вычисление значения <mathtex>b_3g(n+1) = O \left</tex> состоит из вычисления <tex>g(2^{\log_2 n} \log_2 n + \log_2 n\right) = O \left</tex>, проверки неравенства <tex>(n \log_2 n\right) = O\left^{g(n^2\right) } \in \tilde{P}ge n</mathtex>и, возможно, запуска одной из двух внутренних функций, время выполнения которых составляет:

<mathul>b_4<li>для случая <tex>g(n) = b32 i</tex>:<br/><tex>\parbox{0px}{\begin{align*}T(b1n) & \le 2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(x \in \mathrm{SAT})) \le \\ & \le k_1 n(|x|^i + T(g, |x|)+ 2^{|x|}|x|) = O\leftle \\ & \le k_1 n ((\log_2 n)^{g(n)} + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) \le \\ & \le k_1 (n^42 + n^2 \rightlog_2 n + n T(g, \log_2 n)) \in le \\ & \le k_1 (2n^3 + n T(g, \log_2 n));\tildeend{Palign*}}</mathtex></li>

Чтобы построить программу <mathli>p_iдля случая </mathtex> достаточно построить g(n) = 2 i - 1<math/tex>\tilde{p_i}:<br/math>. Из того, что все <mathtex>\tildeparbox{p_i0px}</math> упорядочены по длине, следует, что длина{<math>\tildebegin{p_ialign*}</math> не превосходит <math>ci</math> T(константа зависит от языка описания программыn).Поэтому для построения i-ой программы достаточно перебрать все <math>& \le 2^{ci\log_2 n} (T(x \in \mathrm{SAT}) +1T(g, |f_i(x)|) + T(f_i(x) \in \mathrm{SAT}-1</math> слов с длиной не больше <math>ci</math>)) \le \\и вывести i-ое, являющееся программой. Такой способ требует <math>O & \le k_2 n (2^{ci\log_2 n}i\log_2 n + T(g, \log_2 n) = O(+ 2^{\log_2 n} \log_2 n) = O\le \\ & \le k_2 (n2n^2\log_2 n + n T(g, \log_2 n))</math> времени.\le \\Аналогично можно построить и <math>f_i</math>. Из этого следует & \le k_2 (2n^3 + n T(g, что <math>c_1(\log_2 n)).\end{align*}}</mathtex> и <math/li>c_2(n)</mathul> тоже полиномиальны.

Получаем, что Вычислить <mathtex>T(\log_2 n) = T^{g(n-1) + poly}</mathtex>. Значит, можно за<mathtex>Tk_3 \log_2 g(n) |(\le log_2 n)^{g(n )}|^2 \cdot poly </math>. Поэтому <math>Tle k_3 (g(n) |log_2 n|)^2 log_2 n \in \tilde{P}</math> и <math>A \in Ple k_3 n^3</mathtex>.

Таким образом, <mathtex>f</math> полиномиальна и <math>A T(g, n) \le T(g, n-1) + k (n^3 + n T(g, \in Plog_2 n))</mathtex>.

===Доказательство выполнения свойств Пусть <mathtex>A</math>===ПредположимT(g, что <math>\lim_{n \to \infty}f(n1) = 2id</mathtex>. Это значит, что фунция «застряла» в ветке «иначе» случая два,но из этого следует, что Существует константа <mathtex>SATc \ge d</mathtex> отличается от , для которой при любом <mathtex>L(p_i)n</mathtex> лишь на конечное число элементов. Этоверновлечёт за собой принадлежность <mathtex>SAT</math> к <math>P</math>, что противоречит предположению <math>P c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \ne NPle c n^4</mathtex>.

АналогичноТогда, в случае, если силу <mathtex>\lim_{n \to \infty}fT(ng, 1) = 2i+d \le c \cdot 1^4</mathtex>. Тогда функция «застряла» в ветке «иначе» случая три.Следствием этого является тои неравенства строкой выше, по индукции легко доказать, что <mathtex>SATT(g, n)</mathtex> функцией ограничено сверху <mathtex>p_ic n^4</mathtex> сводится к конечному множеству, что тожепротиворечит предположению то есть <mathtex>g \in \tilde{\mathrm{P }}</tex>, а, в свою очередь, <tex>A \in \ne NPmathrm{P}</mathtex>.}}

Получается, что <math>\lim_{n \to \infty}f(n) = +\infty</math>= Источник ==* ''William Gasarch, но по построению если <math>f</math> неограниченно растет,то <math>L<Lance Fortnow''. [http:/math> не совпадает ни с каким языком <math>L(p_i)</math> и ни одна функция <math>f_i</math> не сводит<math>SAT</math> к <math>L</math>blog.computationalcomplexity. Следовательно, выполняются все три требуемых свойста, и <math>L<org/math> является примеромязыка из <math>NP\setminus(P \cup NPC)<media/math>ladner.pdf Two Proofs of Ladner’s Theorem]