Изменения

==Иллюстрация== Определим язык <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>,не принадлежащих классу <math>P</math>распознаваемых за полиномиальное время, поэтому <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-полным. Пустьэто не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,[[Сведение по Карпу|сводящая по Карпу ]] <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]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу]] к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cap A</tex> удовлетворял следующим условиям: # <tex>L \in \mathrm{NP}</tex> (для этого достаточно, чтобы выполнялось <tex>A \in \mathrm{P}</tex>);# <tex>L \not \in \mathrm{P}</tex>;# <tex>\mathrm{SAT} \not \le L</tex>. Если выполнены все три свойства, то <tex>L \in \mathrm{NP} \setminus (\mathrm{P} \cup \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 \Sigma^*</tex>. Для простоты будем считать, что <tex>|\Sigma| = 2</tex>. Построим такую ''неубывающую'' функцию <tex>g \in \tilde{\mathrm{P}}</tex>, что при <tex>A = \{x \in \Sigma^*: g(|x|) \equiv 0 \pmod{2} \}</tex> для <tex>L</tex> выполняются три перечисленных свойства. === Алгоритм построения g === Положим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex> построим <tex>g(n + 1)</tex> рекурсивно — с помощью <tex>g(0), g(1), \ldots, g(n)</tex>. * Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, то <tex>g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов. * Пусть вычисленное значение <tex>g(n) = 2 i</tex>. Определим <tex>g(n+1)</tex> следующим образом:  for <tex>x</tex> : <tex>|x| \le \log_2 n</tex> if <tex>M_i(x)</tex> and <tex>[g(|x|) \equiv 1 \pmod{2}</tex> or <tex>x \not \in \mathrm{SAT}]</tex> <tex>g(n+1) := g(n)+1</tex> return if <tex>! M_i(x)</tex> and <tex>[g(|x|) \equiv 0 \pmod{2}</tex> and <tex>x \in \mathrm{SAT}]</tex> <tex>g(n+1) := g(n)+1</tex> return <tex>g(n+1) := g(n)</tex>

Будем искать язык * Пусть вычисленное значение <mathtex>Ag(n) = 2 i - 1</mathtex>, удовлетворяющий следующим условиям:#. Определим <math>A \in P</mathtex> g(что влечёт за собой<math>SAT \cap A \in NP</math>n+1)#<math>SAT \cap A \not\in P</math>#<math>SAT \nleqslant SAT \cap A</mathtex>следующим образом:

Если такой язык существует for <tex>x</tex> : <tex>|x| \le \log_2 n, то |f_i(x)| \le \log_2 n<math/tex> if <tex>x \in \mathrm{SAT}</tex>L and <tex>[g(|f_i(x)|) \equiv 1 \pmod{2}</tex> or <tex>f_i(x) \not \in \mathrm{SAT}]</tex> <tex>g(n+1) := A g(n)+1</tex> return if <tex>x \not \in \cap mathrm{SAT}</mathtex> искомым примером множестваиз and <mathtex>NP [g(|f_i(x)|) \equiv 0 \setminus pmod{2}</tex> and <tex>f_i(P x) \in \cup NPCmathrm{SAT}]</tex> <tex>g(n+1) := g(n)+1</tex> return <tex>g(n+1) := g(n)</mathtex>.

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

'''Утверждение 2* Пусть <tex>g(n)</tex> не имеет предела при <tex>n \to \infty</tex>.''' Можно перечислить все Значит, для любой <tex>M_i</tex> в <tex>L</tex> существует элемент, на котором <tex>M_i</tex> «ошибается»; аналогично, для любой полиномиальной функции из <mathtex>f_i</tex> существует элемент, на котором <tex>f_i</tex> неверно сводит <tex>\tildemathrm{PSAT}</mathtex> к <tex>L</tex>. Оба свойства выполнены.

Доказательство аналогично доказательству предыдущего утверждения* Пусть <tex>\lim\limits_{n \to \infty} g(n) = 2i</tex>. Значит, в нашем множестве существует такая машина Тьюринга <tex>M_i</tex>, распознающая <tex>L</tex>, что <tex>\forall x \Rightarrow M_i(x) = [g(|x|) \equiv 0 \pmod{2} \wedge x \in \mathrm{SAT}]</tex>. С одной стороны, <tex>M_i</tex> работает за полином, и <tex>L \in \mathrm{P}</tex>. С другой стороны, по определению <tex>A</tex>, <tex>L</tex> различается с <tex>\mathrm{SAT}</tex> в конечном числе элементов, значит <tex>\mathrm{SAT} \le L</tex>. Получено противоречие с предположением <tex>\mathrm{P} \neq \mathrm{NP}</tex>.

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

Таким образом, при верности предположения <mathtex>A=\left\mathrm{x | f(|x|) \text{ is evenP}\rightneq \mathrm{NP}</mathtex> второе и третье свойства <tex>L</tex>выполнены.

<math>f(0) = f(1) = 0</math>= Время работы алгоритма ===

Определим Проверим выполнение первого свойства языка <mathtex>f(n)L</mathtex>. Для этого рассмотрим два случая:*'''Случай 1:''' достаточно установить полиномиальность <mathtex>f(n-1)=2iA</mathtex>.*: Если существует <math>x</math>Покажем, такой что <mathtex>|x| < \log_2 T(g, n)</mathtex> и отличается от <mathtex>p_i(x) \ne LT(x)</math>g, то <math>f(n) = f(n-1)+1</mathtex>не более, иначе чем на неубывающий полином <mathtex>f(n) = fp(n-1)</mathtex>.*'''Случай 2:''' Из этого будет следовать полиномиальность <mathtex>f(n-1)=2i+1g</mathtex>.*:Если существует <math>x</mathtex>T(g, такой что <math>|x| < \log_2 n</math> и <math>SAT(x) \ne L(f_i(x))</math>, то <math>fle p(n) = f+ p(n-1)+\ldots + p(1</math>, иначе <math>f) \le n p(n) = f\in poly(n-1)</mathtex>.

ПокажемЗаметим, что <mathtex>f \in \tilde{P}</math>. Для упрощения будем считать, что алфавит <math>\Sigma={0,1}</math>.<math>Tg(n) = T(n-1) + a(n)(b_1(n) + b_2(n) + b_3(n) + b_4(n)) + c_1(n) + c2_2(\le n)</mathtex>, где:*по построению для <mathtex>T(n-\ge 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)</math>;*<math>b_2(n)</math> — запуск <math>SAT(x)</math>;*<math>b_3(n)</math> — запуск <math>L(x)</math>;*<math>b_4(n)</math> — запуск <math>L(f_i(x))</math>;*<math>c_1(n)</math> — построение программы <math>p_i</math>;*<math>c_1(n)</math> — построение программы <math>f_i</mathtex>.

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

<mathul>b_1<li>для случая <tex>g(n) \approx= 2 i</tex>:<br/math> что-то, тоже из <mathtex>\tildeparbox{0px}{\begin{align*}T(n) & \le 2^{P\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|) \le \\ & \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^2 + n^2 \log_2 n + n T(g, \log_2 n)) \le \\ & \le k_1 (2n^3 + n T(g, \log_2 n));\end{align*}}</tex></mathli>

<mathli>b_2для случая <tex>g(n) = 2 i - 1</tex>:<br/><tex>\parbox{0px}{\begin{align*}T(n) & \le 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T(g, |f_i(x)|) + T(f_i(x) \approx in \mathrm{SAT})) \le \\ & \le k_2 n (2^{\log_2 n} \log_2 n + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) \le \\ & \le k_2 (2n^2 \log_2 n + n T(g, \log_2 n)) \le \\ & \le k_2 (2n^3 + n T(g, \log_2 n)).\end{align*}}</mathtex>, из <math/li>\tilde{P}</mathul>

Вычислить <mathtex>b_3(\log_2 n) \approx 2^{log_2 g(n)} log_2 n + log_2 n</mathtex>, из можно за<mathtex>k_3 \tildelog_2 g(n) |(\log_2 n)^{Pg(n)}|^2 \le k_3 (g(n) |log_2 n|)^2 log_2 n \le k_3 n^3</mathtex>.

Таким образом,<mathtex>b_4T(g, n) \approx </math> что-то типа <math>b_3le T(g, n-1)</math>, но с оценкой на <math>|f_i+ k (x)|</math>вместо <math>log_2 n</math>^3 + n T(g, из <math>\tilde{P}log_2 n))</mathtex>.

Пусть <mathtex>c_1T(g, 1) = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n)</mathtex> и верно<mathtex>c_2c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \le c n^4</mathtex> тоже полиномиальны.

ПолучаемТогда, что в силу <mathtex>T(ng, 1) = T(n-d \le c \cdot 1) + poly^4</mathtex>. Значит и неравенства строкой выше, по индукции легко доказать, что <mathtex>T(g, n) \le </tex> ограничено сверху <tex>c n \cdot poly ^4</mathtex>. Поэтому , то есть <mathtex>T(n) g \in \tilde{\mathrm{P}}</mathtex> и , а, в свою очередь, <mathtex>A \in \mathrm{P}</mathtex>.}}

В результате всё почти хорошо== Источник ==* ''William Gasarch, Lance Fortnow''.[http://blog.computationalcomplexity.org/media/ladner.pdf Two Proofs of Ladner’s Theorem]